Leetcode 2379. 得到 K 个黑块的最少涂色次数

目录

一、题目内容和对应链接

1.题目对应链接 

2.题目内容

二、我的想法

三、其他人的题解

---

一、题目内容和对应链接

1.题目对应链接 

Leetcode 2379. 得到 K 个黑块的最少涂色次数

2.题目内容

给你一个长度为 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

二、我的想法

1.最开始想的是，遍历 blocks ，先求出最大的连续 "B" 有多少个。如果这个数大于 k 就直接返回 0 ，否则再遍历。

之后又想干脆一次遍历，求出每块的 B 和 W 都有多少个，之后再看两个 B 中间的 W 又多少，连起来能不能满足 k 个数。

大致代码如下：

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:blockslen = len(blocks)maxcontinue = 0listblock = list()write = black = 0for i in range(0, blockslen):if i == 0:if blocks[0] == "W":write += 1flag = "W"else: black += 1flag = "B"else:if blocks[i] == "W":write += 1if black:listblock.append(black)black = 0else:black += 1 if write:listblock.append(write)maxcontinue = max(maxcontinue,black)write = 0if k <= maxcontinue:return 0if black:listblock.append(black)if write:listblock.append(write)print(flag,listblock)

但是明显不太行。

2.看了下题解的第二行字：滑动窗口，还没往下看我就一下子悟了：

我干脆设一个 i 和 j ，i 到 j 的长度为 k ，i 从 0 开始，j 的最长为 blocks 的长度。

就相当于限定 k 个块，这个块每次往后移动 1 下，判断移动过程中限定的字符串中有几个 W ，最小的 W 的个数即为所求

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:blockslen = len(blocks)minhandle = blocksleni = 0 j = i + kwhile j <= blockslen:white = blocks[i:j].count("W")minhandle = min(white, minhandle)i += 1j += 1return minhandle

三、其他人的题解

官方 ： 滑动窗口

ylb ： 滑动窗口

山寨功夫侠 ： 前缀和