一、题目

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/

二、C++解法

我的思路及代码

滑动窗口

采用大小为 k 的窗口，统计当前窗口里面的黑色数量，需要的步骤即为 k 减去当前窗口内黑色的数量，采用 min 来存放当前所需要的最少次数，遍历一次字符串即可。

class Solution {
public:int minimumRecolors(string blocks, int k) {int count;int min;int left,right;count = left = right =0;min = INT_MAX;for(;rightif(blocks[right] == 'B')count++;}min = k-count;for(;rightif(blocks[left] == 'B')count--;if(blocks[right] == 'B')count++;min = min>(k-count)?(k-count):min;}return min;}
};

• 时间复杂度：O(n)，其中 nnn 为字符串 blocks 的长度
• 空间复杂度：O(1)，仅使用常量空间

官方参考代码

和我思路一样

class Solution {
public:int minimumRecolors(string blocks, int k) {int l = 0, r = 0, cnt = 0;while (r < k) {cnt += blocks[r] == 'W' ? 1 : 0;r++;}int res = cnt;while (r < blocks.size()) {cnt += blocks[r] == 'W' ? 1 : 0;cnt -= blocks[l] == 'W' ? 1 : 0;res = min(res, cnt);l++;r++;}return res;}
};

• 时间复杂度：O(n)，其中 nnn 为字符串 blocks 的长度
• 空间复杂度：O(1)，仅使用常量空间