Easy

题目描述

给你一个长度为 n 的字符串 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 的连续黑色块区间所需的最少操作次数。

解题思路

滑动窗口方法（推荐）： 我们可以使用滑动窗口技术来解决这个问题。对于每个长度为 k 的窗口，统计其中白色块（‘W’）的数量，这就是将该窗口全部变成黑色所需的操作次数。我们需要找到所有窗口中白色块数量的最小值。

具体步骤：

  1. 初始化第一个窗口，统计前 k 个字符中白色块的数量
  2. 使用滑动窗口遍历剩余位置：
    • 移除窗口左边的字符影响
    • 添加窗口右边新字符的影响
    • 更新最小操作次数
  3. 返回最小操作次数

暴力方法： 遍历所有可能的长度为 k 的子串，对每个子串计算需要重新涂色的白色块数量，取最小值。时间复杂度为 O(n×k)。

滑动窗口方法的时间复杂度为 O(n)，空间复杂度为 O(1)，是更优的解法。

代码实现

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int n = blocks.length();
        
        // 计算第一个窗口中白色块的数量
        int whiteCount = 0;
        for (int i = 0; i < k; i++) {
            if (blocks[i] == 'W') {
                whiteCount++;
            }
        }
        
        int minOperations = whiteCount;
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边的字符
            if (blocks[i - k] == 'W') {
                whiteCount--;
            }
            // 添加右边的字符
            if (blocks[i] == 'W') {
                whiteCount++;
            }
            minOperations = min(minOperations, whiteCount);
        }
        
        return minOperations;
    }
};

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        n = len(blocks)
        
        # 计算第一个窗口中白色块的数量
        white_count = sum(1 for i in range(k) if blocks[i] == 'W')
        min_operations = white_count
        
        # 滑动窗口
        for i in range(k, n):
            # 移除左边的字符
            if blocks[i - k] == 'W':
                white_count -= 1
            # 添加右边的字符
            if blocks[i] == 'W':
                white_count += 1
            min_operations = min(min_operations, white_count)
        
        return min_operations

public class Solution {
    public int MinimumRecolors(string blocks, int k) {
        int n = blocks.Length;
        
        // 计算第一个窗口中白色块的数量
        int whiteCount = 0;
        for (int i = 0; i < k; i++) {
            if (blocks[i] == 'W') {
                whiteCount++;
            }
        }
        
        int minOperations = whiteCount;
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边的字符
            if (blocks[i - k] == 'W') {
                whiteCount--;
            }
            // 添加右边的字符
            if (blocks[i] == 'W') {
                whiteCount++;
            }
            minOperations = Math.Min(minOperations, whiteCount);
        }
        
        return minOperations;
    }
}

/**
 * @param {string} blocks
 * @param {number} k
 * @return {number}
 */
var minimumRecolors = function(blocks, k) {
    const n = blocks.length;
    
    // 计算第一个窗口中白色块的数量
    let whiteCount = 0;
    for (let i = 0; i < k; i++) {
        if (blocks[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型滑动窗口解法暴力解法
时间复杂度O(n)O(n×k)
空间复杂度O(1)O(1)

其中 n 是字符串 blocks 的长度，k 是目标连续黑色块的数量。

相关题目