[每日一题]2379.得到 K 个黑块的最少涂色次数
2379. 得到 K 个黑块的最少涂色次数 给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 ‘W’ 要么是 ‘B’ ，表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数
输入：blocks = “WBBWWBBWBW”, k = 7 输出：3 解释： 一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。 得到 blocks = “BBBBBBBWBW” 。 可以证明无法用少于 3 次操作得到 7 个连续的黑块。 所以我们返回 3 。
输入：blocks = “WBWBBBW”, k = 2 输出：0 解释： 不需要任何操作，因为已经有 2 个连续的黑块。 所以我们返回 0 。
提示：
- n == blocks.length
- 1 <= n <= 100
- blocks[i] 要么是 ‘W’ ，要么是 ‘B’ 。
- 1 <= k <= n
Solutions
class Solution {
public int minimumRecolors(String blocks, int k) {
int res = 0;
int sum = 0;
int n = blocks.length();
for (int i = 0; i < k; i++) {
char c = blocks.charAt(i);
if (c == 'W') {
sum++;
res++;
}
}
for (int i = k; i < n; i++) {
char c = blocks.charAt(i);
// System.out.println(sum + " " + i);
int op = (c == 'W' ? 1 : 0);
char left = blocks.charAt(i - k);
op += (left == 'W' ? -1 : 0);
sum += op;
res = Math.min(sum, res);
}
return Math.min(res, sum);
}
}
class Solution {
public int minimumRecolors(String blocks, int k) {
char[] chs = blocks.toCharArray();
int cnt = Integer.MAX_VALUE;
for (int i = 0; i <= chs.length - k; i++) {
int tmp = 0;
for (int j = i; j < i + k; j++) {
if (chs[j] == 'W') {
tmp++;
}
}
cnt = Math.min(cnt, tmp);
}
return cnt;
}
}
Ideas
-
滑动窗口
首先题目给出一个下标从 0 开始长度为 n 的字符串 blocks，其中 blocks[i] 是 ′ W ′ 或 ′B ′，分别表示白色块要么是黑色块。现在我们可以执行任意次将一个白色块转变为黑色块的操作，并给出一个整数 k，我们需要返回至少出现一次连续 k 个黑色块的最少操作次数。
我们可以用「滑动窗口」来解决该问题。我们用一个固定大小为 k 的「滑动窗口」表示出现连续 k 个黑色块的区间，我们需要将该区间全部变为黑色块，此时我们需要的操作次数为该区间中白色块的数目，那么我们只需要在「滑动窗口」从左向右移动的过程中维护窗口中白色块的数目，最后返回移动过程中白色块数目的最小值即为我们需要至少出现一次连续 k 个黑色块的最少操作次数。