【每日一题】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中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

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

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

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

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