当前位置: 首页 > news >正文

Leetcode 每日一题 1234. 替换子串得到平衡字符串

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

 

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

目录

题目:

白话讲解:

题例:

题解:

 代码实现:

完结撒花:


本题的核心思想为:滑动窗口(滑动窗口)

忘掉的友友们可以回顾之前的内容进行复习一下 :滑动窗口

题目:

有一个只含有 'Q', 'W', 'E', 'R' 四种字符,且长度为 n 的字符串。

假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。

给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串,则返回 0

白话讲解:

有一个长度为4的倍数的字符串,其中出现四类字符QWER若这四类字符出现的次数为n/4则认为这是一个平衡字符串,返回0

若不为平衡字符串,则需要替换其中连续的子字符串,返回替换最短子字符串的长度.

题例:

输入:s = "QWER"
输出:0
解释:s 已经是平衡的了。
输入:s = "QQWE"
输出:1
解释:我们需要把一个 'Q' 替换成 'R',这样得到的 "RQWE" (或 "QRWE") 是平衡的。
输入:s = "QQQW"
输出:2
解释:我们可以把前面的 "QQ" 替换成 "ER"。
输入:s = "QQQQ"
输出:3
解释:我们可以替换后 3 个 'Q',使 s = "QWER"。

题解:

观察题意可知,以滑动窗口为分界点,若 窗口外的字母每类字母<=n/4 则将窗口内的字母全部替换就满足题意了.

举个例子:WQWRQQW

 当区间内为WQWRQ时,窗口外的字母数如图所示,这时将窗口内的字母全部替换成所缺项,即可符合题意

如图,蓝线是变化的字母,绿线是没有变化的字母(先按下不表) ,这时我们就可以发现,这个子字符串是满足题意的.这个长度为5

我们可以把这个作为答案嘛?显然是不可以的,因为这不是最优解.最简单来看,

当区间内容为QWRQ的时候,也就是左移一个单位,将没有变化的字符串移出去,此时要变化的就是QWRQ

这就体现出了滑动窗口的核心思想:先向右遍历到满足条件的区间,左区间再收缩寻找最优解

 代码实现:

#include <algorithm>
#include<iostream>
#include<string>
using namespace std;
class Solution {
public:int balancedString(string s) {int cnt[26]={0};int n=s.size();for(char c:s)cnt[c-'A']++;int ans=INT_MAX;if(cnt['Q'-'A']==n/4&&cnt['W'-'A']==n/4&&cnt['E'-'A']==n/4&&cnt['R'-'A']==n/4)return 0;//已经排完序for(int i=0,j=0;j<n;j++)//遍历右端点{cnt[s[j]-'A']--;//更新刚刚新加入窗口的元素while(i<=j&&cnt['Q'-'A']<=n/4&&cnt['W'-'A']<=n/4&&cnt['E'-'A']<=n/4&&cnt['R'-'A']<=n/4)//窗口外的所有元素数量都小于等于要求答案{ans=min(ans,j-i+1);//说明当前区间内的所有元素都变换即可满足题意,更新区间cnt[s[i]-'A']++;//寻找最小的情况i++;}}return ans;}
};

完结撒花:

🌈本篇博客的内容【Leetcode 每日一题 1234. 替换子串得到平衡字符串】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

相关文章:

Leetcode 每日一题 1234. 替换子串得到平衡字符串

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…...

【MYSQL中级篇】数据库数据查询学习

&#x1f341;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; 相关文章 文章名文章地址【MYSQL初级篇】入门…...

华为OD机试真题JAVA实现【火星文计算】真题+解题思路+代码(20222023)

🔥系列专栏 华为OD机试(JAVA)真题目录汇总华为OD机试(Python)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出描述示例一输入输出说明解题思路核心知识点Code运行结果版...

Linux基础知识

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…...

Linux 游戏性能谁的 更优秀X.Org还是Wayland!

导读X.Org 和 Wayland 是目前 Linux 平台上的两大主流显示服务器&#xff0c;那么两者在 Linux 游戏性能上谁更优秀呢&#xff1f;国外科技媒体 Phoronix 在 Ubuntu 22.10 上对其进行了多款游戏的实测。评测在运行 GNOME 43.1 的 Ubuntu 22.10 上进行测试&#xff0c;在安装英伟…...

【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

&#x1f451;专栏内容&#xff1a;数据结构⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;日拱一卒&#xff0c;功不唐捐 文章目录一、前言二、时间复杂度1、定义2、大O的渐进表示法3、常见的时间复杂度三、空间复杂度1、定义2、常见的空间复杂度一、前…...

Linux根文件系统移植

目录 一、根文件系统 1.1根文件系统 1.2根文件系统内容 二、根文件系统移植 2.1BusyBox 2.2BusyBox的获取 2.3BusyBox的使用 2.4make menuconfig 2.5编译和安装 2.6修改根文件系统 一、根文件系统 1.1根文件系统 根文件系统是内核启动后挂载的第一个文件系统系统引…...

Three.js 无限平面快速教程【Plane】

Three.js 提供了 Plane 概念来表示在 3d 空间中无限延伸的二维表面。 这对于光标交互很有用&#xff0c;因此你可能需要了解如何设置此平面、将其可视化并根据需要进行调整。 推荐&#xff1a;使用 NSDT场景设计器 快速搭建 3D场景。 Three.js 的 Plane 文档很好而且准确&…...

在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。

实现在线预览PDF文件、图片&#xff0c;并且预览地址不显示文件或图片的真实路径。1、vue使用blob流在线预览PDF、图片&#xff08;包括jpg、png等格式&#xff09;。1、按钮的方法&#xff1a;2、方法详细&#xff1a;&#xff08;此方法可以在发起请求时携带token&#xff0c…...

Allegro如何设置导入Subdrawing可自由选择目录操作指导

Allegro如何设置导入Subdrawing可自由选择目录操作指导 用Allgro做PCB设计的时候,导入Subdrawing是非常常用的功能,在导入Subdrawing的时候,通常需要把Subdrawing文件放在需要导入PCB的相同目录下,不能自由选择,如下图 但是Allegro是支持自由选择目录的,只需按照下方的步…...

SpirngMVC执行原理--自学版

DispatcherServlet表示前置控制器&#xff0c;是整个SpringMVC的控制中心&#xff0c;用户发出请求&#xff0c;DispatcherServlet接收请求并拦截请求HandlerMapper为处理器映射。DispatcherServlet调用。HandlerMapping根据请求url查找HandlerHandlerExecution表示具体的Handl…...

获取savemodel的输入输出节点

saved_model_cli show --dir savemodels --all 结果&#xff1a; MetaGraphDef with tag-set: ‘serve’ contains the following SignatureDefs: signature_def[‘translation_signature’]: The given SavedModel SignatureDef contains the following input(s): inputs[‘i…...

《Learning to Reconstruct Botanical Trees from Single Images》学习从单幅图像重建植物树

读书报告下载https://download.csdn.net/download/weixin_43042683/87448211论文原文https://dl.acm.org/doi/10.1145/3478513.3480525论文视频https://www.bilibili.com/video/BV1cb4y127Vp/?fromseopage&vd_source5212838c127b01db69dcc8b2d27ca5171引言植物存在在室外与…...

vant 4 正式发布,支持暗黑主题,那么是如何实现的呢

2022年10月25日首发于掘金&#xff0c;现在同步到公众号。11. 前言大家好&#xff0c;我是若川。我倾力持续组织了一年多源码共读&#xff0c;感兴趣的可以加我微信 lxchuan12 参与。另外&#xff0c;想学源码&#xff0c;极力推荐关注我写的专栏《学习源码整体架构系列》&…...

MySQL的复制 二

复制是MySQL的一项功能&#xff0c;使服务器能够将更改从一个实例恢复到另一个实例 主服务器&#xff08;master&#xff09;将所有数据和结构更改记录到二进制日志中。二进制日志格式是基于语句的、基于行的和混合的。 从属服务器&#xff08;slave&#xff09;从主服务器请求…...

秒杀项目之秒杀商品展示及商品秒杀

目录前言一、登录方式调整二、生成秒杀订单2.1 绑定秒杀商品2.2 查看秒杀商品2.3 订单秒杀2.3.1 移除seata相关&#xff08;方便测压&#xff09;2.3.2 生成秒杀订单2.3.3 前端页面秒杀测试注意前言 博主博客用到的资源都会同步分享到资源包中 一、登录方式调整 第1步&#xf…...

教育行业需要什么样的数字产品?

数字化转型的浪潮已经席卷了各行各业&#xff0c;不仅出现在互联网、电商、建筑等行业&#xff0c;还应用在了教育行业。数字化的教育ERP软件能够在满足学校需求的基础上&#xff0c;帮助学校完善各类工作流程&#xff0c;提高工作效率。 对于一个拥有多个校区&#xff0c;上万…...

Spring MVC

一、Spring MVC介绍 a. Spring MVC是一个Web框架 b. Spring MVC是基于Servlet API构成的 MVC 是 Model View Controller 的缩写。 MVC 是⼀种思想&#xff0c;⽽ Spring MVC 是对 MVC 思想的具体实现。 学习Spring MVC目标&#xff1a; a.连接功能&#xff1a;将用户&#xff…...

类与对象(上)

类与对象(上) 1.面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间…...

正确安装 torch_geometric库

step1&#xff1a; 查看pytorchcuda 版本 torch-scatter torch-sparse torch-cluster torch-spline-conv 这些关联包要与torch版本匹配。 import torch print(torch.__version__) print(torch.cuda.is_available()) torch.version.cuda或者 pip list查看版本 step2&#xff…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...