【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)

本文主要是介绍【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数(字符串、滑动窗口)

题目描述

给定一个字符串 blocks,其中每个字符代表一个颜色块,可以是 ‘W’(白色)或 ‘B’(黑色)。你需要找到一个至少包含 k 个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k 个黑色块的最少操作次数。

和该题目类似:【每日一题】LeetCode 2024.考试的最大困扰度(字符串、二分查找、前缀和、滑动窗口)

思路分析

这个问题可以通过滑动窗口的方法来解决。我们的目标是在字符串中找到一个长度为 k 的窗口,使得窗口内的黑色块尽可能多,白色块尽可能少。这样,将白色块变成黑色块的操作次数就会最少。

  1. 初始化:首先,我们初始化一个变量 min 来存储最少操作次数,初始值设为最大整数。然后,我们定义两个指针 leftright 来表示窗口的边界,并定义一个变量 count 来记录窗口内白色块的数量。
  2. 填充窗口:我们首先将窗口从左到右扩展到长度 k,同时计算窗口内白色块的数量,并更新 min
  3. 滑动窗口:接着,我们将 right 指针向右移动,每次移动后,如果遇到白色块,则增加 count。同时,将 left 指针向右移动,如果 left 指针指向的块是白色,则减少 count。每次移动后,都更新 min
  4. 返回结果:当 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个黑块的最少涂色次数(字符串、滑动窗口)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146192

相关文章

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①:StringBui