一【题目类别】

滑动窗口

二【题目难度】

简单

三【题目编号】

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.length
1 <= n <= 100
blocks[i] 要么是 ‘W’ ，要么是 ‘B’ 。
1 <= k <= n

七【解题思路】

本题利用经典的滑动窗口的思想
首先计算前k个元素有多少个’W’
然后遍历剩下的元素，以k为“窗口”大小，每次判断一个新进入“窗口”的元素，如果其为"W"，那么需要变化的个数加一，否则不变
上面的步骤相当于“窗口”右移，所以我们要考虑“窗口”最左边的元素，如果“窗口”最左边的元素为"W"，那么将需要变化的个数减一，因为其被移出“窗口”了
每次我们都取最小的值
最后返回结果即可

八【时间频度】

时间复杂度： $O (n)$ ，其中 $n$ 为传入的字符串的长度
空间复杂度： $O (1)$

九【代码实现】

Java语言版

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int sumW = 0;
        for(int i = 0;i<k;i++){
            if(blocks.charAt(i) == 'W'){
                sumW++;
            }
        }
        int res = sumW;
        for(int i = k;i<blocks.length();i++){
            if(blocks.charAt(i) == 'W'){
                sumW += 1;
            }
            if(blocks.charAt(i - k) == 'W'){
                sumW -= 1;
            }
            res = Math.min(res,sumW);
        }
        return res;
    }
}

C语言版

int minimumRecolors(char * blocks, int k)
{
    int sumW = 0;
    for(int i = 0;i<k;i++)
    {
        if(blocks[i] == 'W')
        {
            sumW++;
        }
    }
    int res = sumW;
    for(int i = k;i<strlen(blocks);i++)
    {
        if(blocks[i] == 'W')
        {
            sumW++;
        }
        if(blocks[i - k] == 'W')
        {
            sumW--;
        }
        res = fmin(res,sumW);
    }
    return res;
}

Python语言版

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        sumW = 0
        for i in range(k):
            if blocks[i] == 'W':
                sumW += 1
        res = sumW
        for i in range(k,len(blocks)):
            if blocks[i] == 'W':
                sumW += 1
            if blocks[i - k] == 'W':
                sumW -= 1
            res = min(res,sumW)
        return res

C++语言版

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int sumW = 0;
        for(int i = 0;i<k;i++)
        {
            if(blocks[i] == 'W')
            {
                sumW++;
            }
        }
        int res = sumW;
        for(int i = k;i<blocks.size();i++)
        {
            if(blocks[i] == 'W')
            {
                sumW++;
            }
            if(blocks[i - k] == 'W')
            {
                sumW--;
            }
            res = min(res,sumW);
        }
        return res;
    }
};