算法题记录 11

2209.用地毯覆盖后的最少白色砖块（2106）

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

floor[i] = ‘0’ 表示地板上第 i 块砖块的颜色是 黑色 。
floor[i] = ‘1’ 表示地板上第 i 块砖块的颜色是 白色 。
同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

涉及知识点

动态规划

解决思路

i：还剩下i条地毯。
j：剩余砖块为floor[0]到floor[j]，即j+1块砖。
因此，定义状态为dfs(i,j)，表示用i条地毯覆盖下标在[0,j]中的砖，没被覆盖的白色砖块的最少数目。

接下来，思考如何从一个状态转移到另一个状态。

考虑floor[j]是否覆盖（选或不选）：

不覆盖（不选）：接下来要解决的问题是，用i条地毯覆盖下标在[0,j−1]中的砖，没被覆盖的白色砖块的最少数目，再加上int(floor[j])（刚好白色是1），得dfs(i,j)=dfs(i,j−1)+int(floor[j])。
覆盖（选）：如果i>0，接下来要解决的问题是，用i−1条地毯覆盖下标在[0,j−carpetLen]中的砖，没被覆盖的白色砖块的最少数目，即dfs(i,j)=dfs(i−1,j−carpetLen)。

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        floor = list(map(int, floor))  # 避免在 dfs 中频繁调用 int()
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（一行代码实现记忆化）
        def dfs(i: int, j: int) -> int:
            if j < carpetLen * i:  # 剩余砖块可以全部覆盖
                return 0
            if i == 0:
                return dfs(i, j - 1) + floor[j]
            return min(dfs(i, j - 1) + floor[j], dfs(i - 1, j - carpetLen))
        return dfs(numCarpets, len(floor) - 1)

910.最小差值2（2135）

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

涉及知识点

贪心、枚举

解决思路

很容易想到贪心策略：一起变大、变小对结果没影响，只有小的变大、大的变小才有效果。
为了使用贪心策略，我们对([0],…,[i-1])进行变大，([i-1],…,[-1])进行变小，不断增大i值来更新答案。

class Solution:
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans=nums[-1]-nums[0]
        for x,y in pairwise(nums):
            mx=max(x+k,nums[-1]-k)
            mn=min(nums[0]+k,y-k)
            ans=min(ans,mx-mn)
        return ans

3138.同位字符串连接的最小长度（1979）

给你一个字符串 s ，它由某个字符串 t 和若干 t 的 同位字符串 连接而成。

请你返回字符串 t 的 最小 可能长度。

同位字符串 指的是重新排列一个字符串的字母得到的另外一个字符串。例如，”aab”，”aba” 和 “baa” 是 “aab” 的同位字符串。

涉及知识点

数学、字符串

解决思路

若有多个t，那么s一定形如这样[t0,t1,t2,t3…]，每个t中字母出现次数一致，所以如果对s中各元素出现次数进行统计并求最大公因数，再除以公因数，我们就得到了t中各元素的出现次数，此时t的长度也就确定了。
但是，这样做有个例外，形如aabb的t，按上述方法会提取出aa、bb，最后返回一个2而不是4，为了避免这种情况，我们拿第一个t也就是t0与后面的t进行比较，如果每个t中元素出现次数还是一样，那么就是正确答案，不然继续找次大的公因数。

class Solution:
    def minAnagramLength(self, s: str) -> int:
        n = len(s)
        g = gcd(*Counter(s).values())
        for times in range(g, 1, -1):
            if g % times:
                continue
            k = n // times
            t = sorted(s[:k])
            if all(sorted(s[i - k: i]) == t for i in range(k * 2, n + 1, k)):
                return k
        return n

3255.长度为K的子数组的能量值2（1595）

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续（即 nums[i] + 1 = nums[i + 1]，i < n）且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的 子数组 的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

涉及知识点

滑动窗口

解决思路

秒答题

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        ans=[-1]*(len(nums)-k+1)
        count=0
        for i,x in enumerate(nums):
            count=count+1 if i==0 or x==nums[i-1]+1 else 1
            if count>=k:
                ans[i-k+1]=x
        return ans

2187.完成旅途的最少时间（1641）

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

涉及知识点

数学，二分

解决思路

看似秒答题，我们设目前时间为k，k整除以time中每个元素，将结果加和，如果大于等于totalTrips，那么k就是最小时间。
但是，按for对k递增来找到目标值势必会导致超时。在这题中为了简便运算，应该引入二分法，同时也可以缩小初始搜索区间。

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        f = lambda x: sum(x // t for t in time)
        min_t = min(time)
        avg = (totalTrips - 1) // len(time) + 1
        # bisect_left 需要用左闭右开区间
        left = min_t * avg
        right = min(max(time) * avg, min_t * totalTrips)
        return bisect_left(range(right), totalTrips, left, key=f)

2920.收集所有金币可获得的最大积分（2351）

有一棵由 n 个节点组成的无向树，以 0 为根节点，节点编号从 0 到 n - 1 。给你一个长度为 n - 1 的二维 整数 数组 edges ，其中 edges[i] = [ai, bi] 表示在树上的节点 ai 和 bi 之间存在一条边。另给你一个下标从 0 开始、长度为 n 的数组 coins 和一个整数 k ，其中 coins[i] 表示节点 i 处的金币数量。

从根节点开始，你必须收集所有金币。要想收集节点上的金币，必须先收集该节点的祖先节点上的金币。

节点 i 上的金币可以用下述方法之一进行收集：

收集所有金币，得到共计 coins[i] - k 点积分。如果 coins[i] - k 是负数，你将会失去 abs(coins[i] - k) 点积分。
收集所有金币，得到共计 floor(coins[i] / 2) 点积分。如果采用这种方法，节点 i 子树中所有节点 j 的金币数 coins[j] 将会减少至 floor(coins[j] / 2) 。
返回收集 所有 树节点的金币之后可以获得的最大积分。

涉及知识点

动态规划

解决思路

因为采用方法二会影响到后续节点的积分，导致情况比较复杂，所以数学方法不应讨论，更换为动态规划。

定义dfs(i,j)表示递归到以i为根的子树，在上面已经执行了j次右移的前提下，我们在这棵子树中最多可以得到多少积分。

用「选或不选」来思考，即是否执行右移：

不右移：答案为(coins[i] >> j)−k加上i的每个子树ch的dfs(ch,j)。
右移：答案为coins[i] >> (j+1)加上i的每个子树ch的dfs(ch,j+1)。
两种情况取最大值

设w是coins[i]的二进制长度，那么coins[i]右移w次后就是0了。

在本题的数据范围下，w≤14。

所以如果在递归过程中发现j+1=14，就不执行右移，因为此时dfs(ch,j+1)子树中的每个节点值都要右移14次，算出的结果一定是0。既然都知道递归的结果了，那就不需要递归了。

此外，为避免错把父亲当作儿子，可以额外传入fa表示父节点，遍历i的邻居时，跳过邻居节点是fa的情况。

同时值得注意的是，对于提供“图的边”的题，我们可以用二维数组形式保存下来，方便遍历。

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        g = [[] for _ in coins]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, fa: int) -> int:
            res1 = (coins[i] >> j) - k
            res2 = coins[i] >> (j + 1)
            for ch in g[i]:
                if ch != fa:
                    res1 += dfs(ch, j, i)  # 不右移
                    if j < 13:  # j+1 >= 14 相当于 res2 += 0，无需递归
                        res2 += dfs(ch, j + 1, i)  # 右移
            return max(res1, res2)

        return dfs(0, 0, -1)

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。