图解LeetCode——2379. 得到 K 个黑块的最少涂色次数（难度：简单）

一、题目

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示 白色 和 黑色 。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

二、示例

2.1> 示例 1：

【输入】blocks = "WBBWWBBWBW", k = 7
【输出】3
【解释】一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。得到 blocks = "BBBBBBBWBW" 。可以证明无法用少于 3 次操作得到 7 个连续的黑块。所以我们返回 3 。

2.2> 示例 2：

【输入】blocks = "WBWBBBW", k = 2
【输出】0
【解释】不需要任何操作，因为已经有 2 个连续的黑块。所以我们返回 0 。

提示：

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 要么是 'W' ，要么是 'B' 。
• 1 <= k <= n

三、解题思路

3.1> 思路1：滑动窗口法

通过题目描述，一般来说，我们会首先想到暴力破解法，也就是说，先将blocks转换为字符数组char[] b，然后通过for (int i = 0; i < b.length; i++)进行循环，在循环中的逻辑是，以i为起点，统计连续7个节点中有多少个'W'。这种算法思路很容易理解，但是我们不难发现，这种统计方式会出现重叠遍历的情况，比如i等于0的时候，我们遍历的是从0到6的元素，当i等于1的时候，我们遍历的是从1到7的元素，那么这种重复遍历其实是一种性能的损耗，具体如下图所示：

那么，如何能够避免对相同元素的重复遍历呢？我们其实可以利用滑动窗口的方式，对字符‘W’可以进行动态的统计。具体的操作步骤就是，我们根据方法的第二个入参k，来确定滑动窗口的大小，那么首先统计窗口内W的个数有多少，然后每当窗户向前移动一步的时候，我们要判断出窗口元素（outElement）和新入窗口元素（inElement）。判断详情如下所示：

情况一：outElement与inElement元素相同，则'W'的个数不变。
情况二：outElement='W'，inElement='B'，则'W'的个数减1。
情况三：outElement='B'，inElement='W'，则'W'的个数加1。

上面就是具体的解题思路。下面我们再以blocks = "WBBWWBBWBW", k = 7为例，看看具体的操作步骤是怎么样的？

首先，由于k等于7，所以窗口大小为7个，其中W一共有3个。然后，我们向后移动滑动窗口，发现outElement='W'，inElement='W'，那么符合上面介绍的“情况一”，则字符'W'的个数不变，还是3个。继续移动窗口，发现outElement='B'，inElement='B'，那么符合上面介绍的“情况一”，则字符'W'的个数不变，还是3个。继续移动窗口，发现outElement='B'，inElement='W'，那么符合上面介绍的“情况三”，则字符'W'的个数加1，共有4个。那么由于本题是要求最小的涂色次数，所以返回结果为3。

四、代码实现

4.1> 实现1：滑动窗口法

通过charAt获取指定位置的字符

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

将数组转化为字符数组char[]

class Solution {
    public int minimumRecolors(String blocks, int k) {
        char[] b = blocks.toCharArray();
        int result = 0, painting = 0;
        for (int i = 0; i < b.length; i++) {
            if (i <= k - 1) {
                if (b[i] == 'W') painting++;
                if (i == k - 1) result = painting;
                continue;
            }  
            if (b[i - k] == 'B' && b[i] == 'W') painting++;               
            if (b[i - k] == 'W' && b[i] == 'B') painting--;            
            result = Math.min(result, painting);
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」