用地毯覆盖后的最少白色砖块
难度:
标签:
题目描述
给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。
floor[i] = '0'表示地板上第i块砖块的颜色是 黑色 。floor[i] = '1'表示地板上第i块砖块的颜色是 白色 。
同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。
请你返回没被覆盖的白色砖块的 最少 数目。
示例 1：
输入：floor = "10110101", numCarpets = 2, carpetLen = 2 输出：2 解释： 上图展示了剩余 2 块白色砖块的方案。 没有其他方案可以使未被覆盖的白色砖块少于 2 块。
示例 2：
输入：floor = "11111", numCarpets = 2, carpetLen = 3 输出：0 解释： 上图展示了所有白色砖块都被覆盖的一种方案。 注意，地毯相互之间可以覆盖。
提示：
1 <= carpetLen <= floor.length <= 1000floor[i]要么是'0'，要么是'1'。1 <= numCarpets <= 1000
代码结果
运行时间: 832 ms, 内存: 27.0 MB
/*
* 思路：
* 1. 使用流操作计算白色砖块总数。
* 2. 使用流操作和动态规划更新覆盖后的最小白色砖块数。
*/
import java.util.stream.IntStream;
public class Solution {
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
int n = floor.length();
int[] dp = new int[n + 1];
int whiteCount = IntStream.range(0, n).map(i -> floor.charAt(i) == '1' ? 1 : 0).sum();
for (int i = 0; i < n; i++) {
dp[i + 1] = dp[i] + (floor.charAt(i) == '1' ? 1 : 0);
}
IntStream.range(1, numCarpets + 1).forEach(k -> {
IntStream.iterate(n, i -> i >= 0, i -> i - 1).forEach(i -> {
if (i >= carpetLen) {
dp[i] = Math.min(dp[i], dp[i - carpetLen]);
}
});
});
return dp[n];
}
}解释
方法:
这个题解使用了动态规划的方法来解决问题。定义了一个二维数组 f[i][j]，其中 i 表示使用了 i 条地毯，j 表示考虑到第 j 块砖块时的最小未覆盖白色砖块数。首先初始化 f[0][j] 表示不使用地毯时的未覆盖白色砖块数，即直接统计前 j 个砖块中白色砖块的数量。对于每个 i (1 <= i <= n)，计算使用 i 条地毯覆盖时的情况。具体地，如果放置一条地毯覆盖从 j-carpetLen 到 j 的区间，那么 f[i][j] 可以从 f[i-1][j-carpetLen] 转移过来。也可以选择不放地毯在位置 j，即 f[i][j] 直接从 f[i][j-1] 转移，这时要加上 j 位置的砖块是否为白色。最终，f[n][-1] 就是使用 n 条地毯覆盖所有砖块时的最小未覆盖白色砖块数。
时间复杂度:
O(n*m)
空间复杂度:
O(n*m)
代码细节讲解
🦆
为什么在初始化动态规划数组时只设置 f[0][0] 而不是整个 f[0] 行的所有值？
▷🦆
动态规划转移方程中的 min 函数选择是基于什么考虑？如何确保这种方法可以覆盖所有可能的地毯放置策略？
▷🦆
在动态规划的循环中，为什么 j 的起始值是 carpetLen * i？这样设置有什么特别的意义吗？
▷