本文主要是介绍【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)
题目描述
给定一个字符串 blocks
,其中每个字符代表一个颜色块,可以是 ‘W’(白色)或 ‘B’(黑色)。你需要找到一个至少包含 k
个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k
个黑色块的最少操作次数。
和该题目类似:【每日一题】LeetCode 2024.考试的最大困扰度(字符串、二分查找、前缀和、滑动窗口)
思路分析
这个问题可以通过滑动窗口的方法来解决。我们的目标是在字符串中找到一个长度为 k
的窗口,使得窗口内的黑色块尽可能多,白色块尽可能少。这样,将白色块变成黑色块的操作次数就会最少。
- 初始化:首先,我们初始化一个变量
min
来存储最少操作次数,初始值设为最大整数。然后,我们定义两个指针left
和right
来表示窗口的边界,并定义一个变量count
来记录窗口内白色块的数量。 - 填充窗口:我们首先将窗口从左到右扩展到长度
k
,同时计算窗口内白色块的数量,并更新min
。 - 滑动窗口:接着,我们将
right
指针向右移动,每次移动后,如果遇到白色块,则增加count
。同时,将left
指针向右移动,如果left
指针指向的块是白色,则减少count
。每次移动后,都更新min
。 - 返回结果:当
right
指针到达字符串末尾时,循环结束。此时,min
存储的就是最少操作次数。
输入示例
示例 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
代码实现
class Solution {public int minimumRecolors(String blocks, int k) {int min = Integer.MAX_VALUE; // 初始化最少操作次数为最大整数int left = 0, right = 0; // 定义左右指针int count = 0; // 记录窗口内白色块的数量// 填充窗口直到长度为 kfor (right = 0; right < k; right++) {if (blocks.charAt(right) == 'W') {count++; // 如果是白色块,则增加 count}}min = Math.min(count, min); // 更新最小操作次数// 开始滑动窗口for (right = k; right < blocks.length(); right++) {if (blocks.charAt(right) == 'W') {count++; // 如果新增的块是白色,则增加 count}if (blocks.charAt(left) == 'W') {count--; // 如果移除的块是白色,则减少 count}left++; // 移动左指针min = Math.min(count, min); // 更新最小操作次数}return min; // 返回最少操作次数}
}
这篇关于【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!