class Solution {
public:
int minimumRecolors(string blocks, int k) {
}
};
2379. 得到 K 个黑块的最少涂色次数
给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
示例 1：
输入：blocks = "WBBWWBBWBW", k = 7 输出：3 解释： 一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。 得到 blocks = "BBBBBBBWBW" 。 可以证明无法用少于 3 次操作得到 7 个连续的黑块。 所以我们返回 3 。
示例 2：
输入：blocks = "WBWBBBW", k = 2 输出：0 解释： 不需要任何操作，因为已经有 2 个连续的黑块。 所以我们返回 0 。
提示：
n == blocks.length1 <= n <= 100blocks[i] 要么是 'W' ，要么是 'B' 。1 <= k <= n原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2023-03-09 09:21:28
class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
ans = cnt = blocks[:k].count('W')
for i in range(k, len(blocks)):
cnt += blocks[i] == 'W'
cnt -= blocks[i - k] == 'W'
ans = min(ans, cnt)
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-03-09 09:20:27
func minimumRecolors(blocks string, k int) int {
cnt := strings.Count(blocks[:k], "W")
ans := cnt
for i := k; i < len(blocks); i++ {
if blocks[i] == 'W' {
cnt++
}
if blocks[i-k] == 'W' {
cnt--
}
if ans > cnt {
ans = cnt
}
}
return ans
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.5 MB, 提交时间: 2023-03-09 09:20:03
class Solution {
public int minimumRecolors(String blocks, int k) {
int cnt = 0;
for (int i = 0; i < k; ++i) {
cnt += blocks.charAt(i) == 'W' ? 1 : 0;
}
int ans = cnt;
for (int i = k; i < blocks.length(); ++i) {
cnt += blocks.charAt(i) == 'W' ? 1 : 0;
cnt -= blocks.charAt(i - k) == 'W' ? 1 : 0;
ans = Math.min(ans, cnt);
}
return ans;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-03-09 09:16:49
func minimumRecolors(blocks string, k int) int {
n := len(blocks)
ans := 100
for i := 0; i < n-k+1; i++ {
ans = min(ans, strings.Count(blocks[i:i+k], "W"))
}
return ans
}
func min(x, y int) int { if x < y { return x }; return y }
python3 解法, 执行用时: 28 ms, 内存消耗: 15 MB, 提交时间: 2022-08-23 10:39:53
class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
# 滑动窗口，窗口长度为k；
# 统计窗口内的白色块的最小个数即可；
n = len(blocks)
ans = 100
for i in range(0, n-k+1):
ans = min(ans, blocks[i:i+k].count('W'))
return ans