当前位置：首页 > article >正文

Leetcode2209：用地毯覆盖后的最少白色砖块

article 2025/2/25 4:53:22

题目描述：

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

floor[i] = '0' 表示地板上第 i 块砖块的颜色是黑色。
floor[i] = '1' 表示地板上第 i 块砖块的颜色是白色。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条黑色的地毯，每一条黑色的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余白色砖块的数目最小。地毯相互之间可以覆盖。

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

代码思路：

步骤 1: 初始化

变量定义：
- n：地板字符串的长度。
- dp：一个长度为 n 的数组，dp[i] 表示到位置 i 为止，未铺地毯时的白色瓷砖总数。
计算前缀和：
- dp[0] 初始化为地板字符串第一个字符对应的数字（即 int(floor[0])）。
- 通过遍历地板字符串，计算从起始位置到每个位置 i 的白色瓷砖总数（前缀和）。

步骤 2: 状态转移

滚动数组：
- 使用一个滚动数组 dp2 来存储尝试铺每条新地毯后的白色瓷砖数量。
- 每次尝试铺地毯时，都会重新计算 dp2，然后将 dp2 的值赋给 dp 以更新状态。
地毯覆盖：
- 遍历每个可能的地毯覆盖位置 j，从 carpetLen*i 开始（即第 i 条地毯开始覆盖的位置）。
- 对于每个位置 j，计算两种情况下的最小白色瓷砖数量：
  - 不铺当前地毯：dp2[j-1] + int(floor[j])，即继承前一个位置的状态并加上当前位置的白色瓷砖数量。
  - 铺当前地毯：dp[j-carpetLen]，即使用地毯覆盖从 j-carpetLen 到 j 的区域，白色瓷砖数量等于 j-carpetLen 位置的状态值（因为地毯覆盖的区域不包含白色瓷砖）。
更新状态：
- 对于每个 j，选择上述两种情况中的最小值作为 dp2[j] 的值。
- 遍历完所有可能的地毯覆盖位置后，将 dp2 的值赋给 dp，以便在下一次迭代中使用。

步骤 3: 返回结果

最后，dp[-1] 存储了整个地板在铺完所有地毯后的最少白色瓷砖数量，将其作为结果返回。

代码实现：

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        
        n = len(floor)
        dp = [0] * n
        
        # 初始化：未使用地毯【前缀和】
        dp[0] = int(floor[0])
        for i in range(1, n):
            dp[i] = dp[i-1] + int(floor[i])
        
        # 状态转移：尝试使用地毯【滚动数组优化】
        for i in range(1, numCarpets+1):    # 使用的地毯数目i
            dp2 = [0] * n                   # 滚动数组
            # carpetLen*i 之前的位置均被地毯覆盖，白色砖块数目均为0
            for j in range(carpetLen*i, n): 
                # 在砖块j处 【未使用地毯】 和 【使用地毯】 的最小值
                dp2[j] = min(dp2[j-1]+int(floor[j]), dp[j-carpetLen])
            dp = dp2
        
        return  dp[-1]

查看全文

http://www.kler.cn/a/559875.html