leetcode 周赛

leetcode 周赛的记录

leetcode_周赛

第 360 周赛

2833.距离原点最远的点

思路：转换题目就是 L 与 R 的绝对值差值最大值，加上 _ 的数目

2834. 找出美丽数组的最小和

思路：这题可以使用数位 DP 去做，比赛时采用的是分类讨论也不是很复杂

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        if n <= (target // 2):
            return sum(range(1,n+1))
        else:
            temp = list(range(1,target//2 + 1))
            for i in range(n-target//2):
                temp.append(target+i)
            return sum(temp)

2835. 使子序列的和等于目标的最少操作次数

思路：这题本身比赛时，思路是正确的，想到了使用二进制去解决这个题，包括用低位求和，高位去除等思路。卡在了一是没想清楚从低到高还是从高到低，二是如何低位求和时从数组中删除已经使用的元素。第一一定是从低到高，因为在遍历数组过程中，需要遍历的是求和的，高位不需要。二是使用 mask 位置来进行 & 操作即可让 target-已经被求和的数 ，且使用 Counter 统计元素个数以及自动排序，确实是没想到。

class Solution:
    def minOperations(self, nums: List[int], target: int) -> int:
        if sum(nums) < target:
            return -1
        cnt = Counter(nums)
        ans = s = i = 0
        while 1 << i <= target:
            s += cnt[1 << i] << i
            mask = (1 << (i + 1)) - 1
            i += 1
            if s >= target & mask:
                continue
            ans += 1  # 一定要找更大的数操作
            while cnt[1 << i] == 0:
                ans += 1  # 还没找到，继续找更大的数
                i += 1
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/solutions/2413344/tan-xin-by-endlesscheng-immn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2836. 在传球游戏中最大化函数值

思路：当时想的首先就是确定起点与 K，最后的结果是固定的。所以想的是递归是否可行，仔细想了一下是不可以的，因为即使前面是最大的，你也没办法判断转移状态是否是最大得。爆破更是不可能的，因为 k 的范围非常大，起点范围也很大。所以没想清楚怎么做，看灵神提到了一个树上倍增的思想，我觉得有点类似快速幂的想法。将一个数拆成 2 的幂的和，用空间换取时间，使用二维数组进行存储。

 class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        n = len(receiver)
        m = k.bit_length() - 1
        pa = [[(p, p)] + [None] * m for p in receiver]
        for i in range(m):
            for x in range(n):
                p, s = pa[x][i]
                pp, ss = pa[p][i]
                pa[x][i + 1] = (pp, s + ss)  # 合并节点值之和

        ans = 0
        for i in range(n):
            x = sum = i
            for j in range(m + 1):
                if (k >> j) & 1:  # k 的二进制从低到高第 j 位是 1
                    x, s = pa[x][j]
                    sum += s
            ans = max(ans, sum)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/solutions/2413298/shu-shang-bei-zeng-by-endlesscheng-xvsv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第 361 周赛

7020. 统计对称整数的数目

思路：这题当时因为给的范围特别小，我直接把所有的满足要求的数打印出来。灵神则是通过，遍历 Low High 直接对比两位。当时做这个题的时候，总觉得是有规律的，按道理应该是可以减少时间复杂度的。

class Solution:
    def countSymmetricIntegers(self, low: int, high: int) -> int:
        ans = 0
        for i in range(low, high + 1):
            s = str(i)
            n = len(s)
            ans += n % 2 == 0 and sum(map(int, s[:n // 2])) == sum(map(int, s[n // 2:]))
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-symmetric-integers/solutions/2424088/mei-ju-by-endlesscheng-oo2d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2844. 生成特殊数字的最少操作

思路：这题思路是很清晰的，保证最后两位是 00 25 50 75 即可，但是我在写的时候从右开始遍历的时候，是手写的逻辑，所以中间调试等走了一些弯度。灵神直接使用 rfind() 函数，只能说还是不了解，如果知道有这个函数，真的会省很多事儿。

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        def f(tail: str) -> int:
            i = num.rfind(tail[1])
            if i < 0: return n
            i = num.rfind(tail[0], 0, i)  # 写成 num[:i].rfind(tail[0]) 会产生额外的切片空间
            if i < 0: return n
            return n - i - 2
        return min(n - ('0' in num), f("00"), f("25"), f("50"), f("75"))

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/solutions/2424068/mei-ju-shan-chu-hou-yi-00255075-jie-wei-zhjlu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2845. 统计趣味子数组的数目

思路：首先得把题目进行一个转换，转换成子序列和，而这中间又涉及一个如何把（l,r）之间的和弄出来，这边灵神的思路是再保留一个 list，元素 i 就是子序列前 i 个元素的和，真的是非常妙呀！要擅长使用过 Counter() 代表哈希表

class Solution:
    def countInterestingSubarrays(self, nums: List[int], mod: int, k: int) -> int:
        cnt = Counter([0])  # 把 s[0]=0 算进去
        ans = s = 0
        for x in nums:
            s += x % mod == k
            ans += cnt[(s - k) % mod]  # Python 取模可以把负数自动转成非负数
            cnt[s % mod] += 1
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/count-of-interesting-subarrays/solutions/2424063/qian-zhui-he-ha-xi-biao-fu-ti-dan-by-end-74bb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2846. 边权重均等查询

思路：超出能力范围，但是需要复习一些树相关的模版

第 363 周赛

2848. 与车相交的点

思路：这题我做的时候的思路是通过维护一个状态 list，通过遍历来进行置 1，就是爆破的思路。而在灵神思路他提到了，差分数组这个思路，也就是说不用去遍历 start，end。而是只需要设置 start、end两个位置即可，节省了很多时间

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        max_end = max(end for _, end in nums)
        diff = [0] * (max_end + 2)
        for start, end in nums:
            diff[start] += 1
            diff[end + 1] -= 1
        return sum(s > 0 for s in accumulate(diff))

作者：灵茶山艾府
链接：https://leetcode.cn/problems/points-that-intersect-with-cars/solutions/2435384/chai-fen-shu-zu-xian-xing-zuo-fa-by-endl-3xpm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2849. 判断能都在给定的时间到达单元格

思路：这题本质上不是一个什么算法题，因为它是一个思路题，为啥好说的，和灵神代码一样

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        if sx == fx and sy == fy:
            return t != 1
        return max(abs(sx - fx), abs(sy - fy)) <= t

作者：灵茶山艾府
链接：https://leetcode.cn/problems/determine-if-a-cell-is-reachable-at-a-given-time/solutions/2435321/xian-xie-zhao-zou-zai-zhi-zou-ran-hou-za-lkxu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2850. 将石头分散到网格图的最少移动次数

思路：这题目在思考的时候，我思考是一个枚举的题目，但是没有想好如何去枚举，也没接触过全排列。这里可以使用 permutations() 函数.

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        from_ = []
        to = []
        for i, row in enumerate(grid):
            for j, cnt in enumerate(row):
                if cnt > 1:
                    from_.extend([(i, j)] * (cnt - 1))
                elif cnt == 0:
                    to.append((i, j))

        ans = inf
        for from2 in permutations(from_):
            total = 0
            for (x1, y1), (x2, y2) in zip(from2, to):
                total += abs(x1 - x2) + abs(y1 - y2)
            ans = min(ans, total)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435313/tong-yong-zuo-fa-zui-xiao-fei-yong-zui-d-iuw8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2851. 字符串转换

思路：首先得想明白他的操作，她转换字符串其实就是循环右移字符串。接着想明白 DP 的状态转移方程，再去想如何取值，涉及到 KMP算法。而在 DP 过程中，可以使用快速幂加快时间。

class Solution:
    def numberOfWays(self, s, t, k):
        n = len(s)
        c = self.kmp_search(s + s[:-1], t)
        m = [
            [c - 1, c],
            [n - c, n - 1 - c]
        ]
        m = self.pow(m, k)
        return m[0][s != t]

作者：灵茶山艾府
链接：https://leetcode.cn/problems/string-transformation/solutions/2435348/kmp-ju-zhen-kuai-su-mi-you-hua-dp-by-end-vypf/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第 364 周赛

2864.最大二进制奇数

思路：这题目较为简单，就是找对思路，利用 count 计算0、1 个数，返回即可

2865.美丽塔 I

思路：这个题目，艾神强调了 leetcode 中计算次数大概在 10^6 10^7 附近，题目逻辑不是很复杂，我单独写了一个函数，计算假如把当前位置当峰顶，计算返回值多少。然后遍历数组，不是全遍历，遍历比前一个值大的位置，返回最大的即可。思路来说和艾神的暴力做法思路一致，但是在写法上艾神更加简洁。首先再次使用了 enumerate() 函数，这样就不用单独写一个函数逻辑，并设置更多的参数等。第二个逻辑没有他简洁，使用 min 维护一个变量便解决了问题，而不是我那样另设置一个数组。

for i in range(n-1,-1,-1):
    x = a[i]

等价于

for i,x in enumerate(a):

2866.美丽塔 II

思路：同样的题目，需要降低时间复杂度。其实我在自己写的时候已经体现出了栈的思想。使用单调栈，通过.pop 与 .append 来实现栈的弹入弹出。直接 1516ms 变成了 64ms

class Solution:
    def maximumSumOfHeights(self, a: List[int]) -> int:
        n = len(a)
        suf = [0] * (n + 1)
        st = [n]  # 哨兵
        s = 0
        for i in range(n - 1, -1, -1):
            x = a[i]
            while len(st) > 1 and x <= a[st[-1]]:
                j = st.pop()
                s -= a[j] * (st[-1] - j)  # 撤销之前加到 s 中的
            s += x * (st[-1] - i)  # 从 i 到 st[-1]-1 都是 x
            suf[i] = s
            st.append(i)

        ans = s
        st = [-1]  # 哨兵
        pre = 0
        for i, x in enumerate(a):
            while len(st) > 1 and x <= a[st[-1]]:
                j = st.pop()
                pre -= a[j] * (j - st[-1])  # 撤销之前加到 pre 中的
            pre += x * (i - st[-1])  # 从 st[-1]+1 到 i 都是 x
            ans = max(ans, pre + suf[i + 1])
            st.append(i)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/WhhMVw/view/h8u9cM/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2867.统计树中的合法路径数目

思路：题目我看都没看，树相关的算法主要抱着学习角度去看，其实就是图相关的算法很类似。学习到了判断质数的算法，需要注意的是从 i*i 开始，而不是 i，因为之前肯定遍历过了。

# 标记 10**5 以内的质数
MX = 10 ** 5 + 1
is_prime = [True] * MX
is_prime[1] = False
for i in range(2, isqrt(MX) + 1):
    if is_prime[i]:
        for j in range(i * i, MX, i):
            is_prime[j] = False

class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        def dfs(x: int, fa: int) -> None:
            nodes.append(x)
            for y in g[x]:
                if y != fa and not is_prime[y]:
                    dfs(y, x)

        ans = 0
        size = [0] * (n + 1)
        for x in range(1, n + 1):
            if not is_prime[x]:  # 跳过非质数
                continue
            s = 0
            for y in g[x]:  # 质数 x 把这棵树分成了若干个连通块
                if is_prime[y]:
                    continue
                if size[y] == 0:  # 尚未计算过
                    nodes = []
                    dfs(y, -1)  # 遍历 y 所在连通块，在不经过质数的前提下，统计有多少个非质数
                    for z in nodes:
                        size[z] = len(nodes)
                # 这 size[y] 个非质数与之前遍历到的 s 个非质数，两两之间的路径只包含质数 x
                ans += size[y] * s
                s += size[y]
            ans += s  # 从 x 出发的路径
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/WhhMVw/view/h8u9cM/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第 368 周赛

2908、2909 元素和最小的山形三元组

思路：第一题和第二题知识数字范围不同，但是思路一样，我们遍历山峰，但是关键在于如何对于左右两边的值进行最小的取值，其实右边可以从右往左，用一个变量保留最小的数，左边同理。其次记住 inf 的使用

class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        suf[-1] = nums[-1]
        for i in range(n - 2, 1, -1):
            suf[i] = min(suf[i + 1], nums[i])

        ans = inf
        pre = nums[0]
        for j in range(1, n - 1):
            if pre < nums[j] > suf[j + 1]:
                ans = min(ans, pre + nums[j] + suf[j + 1])
            pre = min(pre, nums[j])
        return ans if ans < inf else -1

2910 合法分组的最少组数

思路：将这个问题转换成了一个数学问题，如下图所示，所以 leetcode 问题一定要先将他转换成数学问题

class Solution:
    def minGroupsForValidAssignment(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        for k in range(min(cnt.values()), 0, -1):
            ans = 0
            for c in cnt.values():
                q, r = divmod(c, k)
                if q < r:
                    break
                ans += (c + k) // (k + 1)
            else:
                return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-number-of-groups-to-create-a-valid-assignment/solutions/2493313/ben-ti-zui-jian-dan-xie-fa-pythonjavacgo-t174/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2911 得到 K 个半回文串的最少修改次数

思路：是一个划分型 DP 问题，如下图所示，需要先进行预处理对于判断字符串变成半回文字符串需要多少步形成一个函数。

# 预处理每个数的真因子，时间复杂度 O(MX*logMX)
MX = 201
divisors = [[] for _ in range(MX)]
for i in range(1, MX):
    for j in range(i * 2, MX, i):
        divisors[j].append(i)

def get_modify(s: str) -> int:
    res = n = len(s)
    for d in divisors[n]:
        cnt = 0
        for i0 in range(d):
            i, j = i0, n - d + i0
            while i < j:
                cnt += s[i] != s[j]
                i += d
                j -= d
        res = min(res, cnt)
    return res

class Solution:
    def minimumChanges(self, s: str, k: int) -> int:
        n = len(s)
        modify = [[0] * n for _ in range(n - 1)]
        for left in range(n - 1):
            for right in range(left + 1, n):  # 半回文串长度至少为 2
                modify[left][right] = get_modify(s[left: right + 1])

        @cache
        def dfs(i: int, j: int) -> int:
            if i == 0:
                return modify[0][j]
            return min(dfs(i - 1, L - 1) + modify[L][j] for L in range(i * 2, j))
        return dfs(k - 1, n - 1)

作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-changes-to-make-k-semi-palindromes/solutions/2493147/yu-chu-li-ji-yi-hua-sou-suo-by-endlessch-qp47/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。