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,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 我会一直往里填充内容哒! &…...
【MYSQL中级篇】数据库数据查询学习
🍁博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 相关文章 文章名文章地址【MYSQL初级篇】入门…...
华为OD机试真题JAVA实现【火星文计算】真题+解题思路+代码(20222023)
🔥系列专栏 华为OD机试(JAVA)真题目录汇总华为OD机试(Python)真题目录汇总华为OD机试(C++)真题目录汇总华为OD机试(JavaScript)真题目录汇总文章目录 🔥系列专栏题目输入输出描述示例一输入输出说明解题思路核心知识点Code运行结果版...
Linux基础知识
♥️作者:小刘在C站 ♥️个人主页:小刘主页 ♥️每天分享云计算网络运维课堂笔记,努力不一定有收获,但一定会有收获加油!一起努力,共赴美好人生! ♥️夕阳下,是最美的绽放࿰…...
Linux 游戏性能谁的 更优秀X.Org还是Wayland!
导读X.Org 和 Wayland 是目前 Linux 平台上的两大主流显示服务器,那么两者在 Linux 游戏性能上谁更优秀呢?国外科技媒体 Phoronix 在 Ubuntu 22.10 上对其进行了多款游戏的实测。评测在运行 GNOME 43.1 的 Ubuntu 22.10 上进行测试,在安装英伟…...
【数据结构】算法的复杂度分析:让你拥有未卜先知的能力
👑专栏内容:数据结构⛪个人主页:子夜的星的主页💕座右铭:日拱一卒,功不唐捐 文章目录一、前言二、时间复杂度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 空间中无限延伸的二维表面。 这对于光标交互很有用,因此你可能需要了解如何设置此平面、将其可视化并根据需要进行调整。 推荐:使用 NSDT场景设计器 快速搭建 3D场景。 Three.js 的 Plane 文档很好而且准确&…...
在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。
实现在线预览PDF文件、图片,并且预览地址不显示文件或图片的真实路径。1、vue使用blob流在线预览PDF、图片(包括jpg、png等格式)。1、按钮的方法:2、方法详细:(此方法可以在发起请求时携带token,…...
Allegro如何设置导入Subdrawing可自由选择目录操作指导
Allegro如何设置导入Subdrawing可自由选择目录操作指导 用Allgro做PCB设计的时候,导入Subdrawing是非常常用的功能,在导入Subdrawing的时候,通常需要把Subdrawing文件放在需要导入PCB的相同目录下,不能自由选择,如下图 但是Allegro是支持自由选择目录的,只需按照下方的步…...
SpirngMVC执行原理--自学版
DispatcherServlet表示前置控制器,是整个SpringMVC的控制中心,用户发出请求,DispatcherServlet接收请求并拦截请求HandlerMapper为处理器映射。DispatcherServlet调用。HandlerMapping根据请求url查找HandlerHandlerExecution表示具体的Handl…...
获取savemodel的输入输出节点
saved_model_cli show --dir savemodels --all 结果: 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日首发于掘金,现在同步到公众号。11. 前言大家好,我是若川。我倾力持续组织了一年多源码共读,感兴趣的可以加我微信 lxchuan12 参与。另外,想学源码,极力推荐关注我写的专栏《学习源码整体架构系列》&…...
MySQL的复制 二
复制是MySQL的一项功能,使服务器能够将更改从一个实例恢复到另一个实例 主服务器(master)将所有数据和结构更改记录到二进制日志中。二进制日志格式是基于语句的、基于行的和混合的。 从属服务器(slave)从主服务器请求…...
秒杀项目之秒杀商品展示及商品秒杀
目录前言一、登录方式调整二、生成秒杀订单2.1 绑定秒杀商品2.2 查看秒杀商品2.3 订单秒杀2.3.1 移除seata相关(方便测压)2.3.2 生成秒杀订单2.3.3 前端页面秒杀测试注意前言 博主博客用到的资源都会同步分享到资源包中 一、登录方式调整 第1步…...
教育行业需要什么样的数字产品?
数字化转型的浪潮已经席卷了各行各业,不仅出现在互联网、电商、建筑等行业,还应用在了教育行业。数字化的教育ERP软件能够在满足学校需求的基础上,帮助学校完善各类工作流程,提高工作效率。 对于一个拥有多个校区,上万…...
Spring MVC
一、Spring MVC介绍 a. Spring MVC是一个Web框架 b. Spring MVC是基于Servlet API构成的 MVC 是 Model View Controller 的缩写。 MVC 是⼀种思想,⽽ Spring MVC 是对 MVC 思想的具体实现。 学习Spring MVC目标: a.连接功能:将用户ÿ…...
类与对象(上)
类与对象(上) 1.面向过程和面向对象初步认识 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。 C是基于面向对象的,关注的是对象,将一件事情拆分成不同的对象,靠对象之间…...
正确安装 torch_geometric库
step1: 查看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ÿ…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

