Leetcode-每日一题1234. 替换子串得到平衡字符串(滑动窗口 + 哈希表)

题目链接:https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/
思路
题目意思
这题意思是一个只含有[Q, W, E, R] 四个字符的字符串s且长度一定是 4的倍数, 需要你通过替换子串,使他变成一个「平衡字符串」,也就是字符串s内四个字符的数量都相等。
首先要仔细审题,我刚开始是以为计算需要替换的字符的数量,秒wa,仔细阅读发现是替换连续子串,需要找到一个最小长度的替换连续子串,第一反应就是滑动窗口或者双指针。
算法小课堂
滑动窗口:滑动窗口是双指针的一种特例,可以称为左右指针,在任意时刻,只有一个指针运动,而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。
滑动窗口的时间复杂度是线性的,时间复杂度一般为O(n),滑动窗口的左右边界都不会向左滑动,向左滑动等于走回头路,是一种回溯的算法,很可能会陷入死循环。滑动窗口是一种全遍历问题,一定会遍历到末尾的。
方法:滑动窗口 + 哈希表
刚开始我们用哈希表统计出四个字符的数量,我们需要满足「平衡字符串」,所以定义一个 check函数 判断四个字符数量小于等于 n / 4。
- 如果原始的 s 就是 「平衡字符串」,则返回 0。
- 如果不是,接下来就是用滑动窗口来遍历字符串,找到待替换子串,来维护区间 [l,r) :
- 当前 l 指针不动, 通过内循环移动 r 指针,循环条件 r 指针需小于字符串s长度并且
check函数满足,直到找到待替换子串。 - 如果找到了使得条件被满足的 r,我们用 r−l 来更新答案 ans,当前 r 指针不动,并使得 l向右移动一个单位进行下一次枚举,通过外循环移动 l 指针, 循环条件 l 指针需小于字符串s长度,使当前代替换子串合法并且最小。
- 直到 r 指针移动到大于等于字符串s长度的位置,且
check函数不满足,退出循环。
- 当前 l 指针不动, 通过内循环移动 r 指针,循环条件 r 指针需小于字符串s长度并且
代码示例
func balancedString(s string) int {n := len(s)mp := make(map[byte]int)for _, v := range s {mp[byte(v)]++}// 判断当前字符串是否是平衡字符串check := func() bool {if mp['Q'] > n / 4 || mp['W'] > n / 4 ||mp['E'] > n / 4 || mp['R'] > n / 4 {return false}return true}if check() {return 0}r, ans := 0, len(s)// 滑动窗口for l, c := range s {for r < n && !check() {mp[s[r]]--r++}// 如果上面循环是 r >= n 条件退出,// 表示现在的连续子串是不满足替换条件的,可以直接退出,避免影响正确答案if !check() {break}ans = min(ans, r - l)mp[byte(c)]++}return ans
}func min(a, b int) int {if a > b {return b}return a
}

复杂度分析
- 时间复杂度:O(n),其中n表示字符串s的长度,记录四个字符的数量需要遍历字符串s,所需时间为O(n),滑动窗口时间是线性的,所以所需时间也为O(n)。
- 空间复杂度:O(1),不需要额外申请空间。
相关文章:
Leetcode-每日一题1234. 替换子串得到平衡字符串(滑动窗口 + 哈希表)
题目链接:https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/ 思路 题目意思 这题意思是一个只含有[Q, W, E, R] 四个字符的字符串s且长度一定是 4的倍数, 需要你通过替换子串,使他变成一个「平衡字符…...
linux命令小结-查看日志命令
一、查看日志命令cat查看文件 vi编辑后可以用cat进行查看保存是否成功1)cat -n alert_monitor.log2)cat -n alert_monitor.log | tail -n 100 | head -n 20 //查询100行之后的日志,且在100行之后里再查前20条日志more 可以通过回撤键翻页mor…...
Java知识点细节简易汇总——(8)枚举和注解+Java面向对象高级作业
一、枚举 自定义枚举 当我们使用 enum 关键字开发一个枚举类时,默认会继承 Enum 类, 而且是一个 final 类[如何证明],老师使用 javap 工具来演示传统的 public static final Season2 SPRING new Season2(“春天”, “温暖”); 简化成 SPRING(“春天”, “温暖”)…...
快速上手JVM- Java Virtual Machine面试不用慌
一、JVM的定义 JVM是Java Virtual Machine(Java虚拟机)的缩写,JVM是一种用于计算设备的规范,它是一个虚构出来的计算机,是通过在实际的计算机上仿真模拟各种计算机功能来实现的。 引入Java语言虚拟机后,J…...
安警官的IP地址是怎样定位到莽村附近的?
要说最近大火的电视剧非《狂飙》莫属。电视剧《狂飙》自开播以来,一举超过《三体》《去有风的地方》等先播电视剧,收视率一路“狂飙”,牢牢占据近期的收视冠军。 在剧中,张译扮演一名坚持公平、正义与理想的人民警察“安欣”&…...
STL中重要容器vector总结
你要尽全力保护你的梦想。那些嘲笑你的人,他们必定会失败,他们想把你变成和他们一样的人。如果你有梦想的话,就要努力去实现。 ——《当幸福来敲门》引言:C中STL里面的容器用法很巧妙,可以解决很多复杂的模型ÿ…...
11_会话原理与实现流程
1、会话的基本知识 # 会话## 1.会话是什么?客户端与服务器之间的对话交流## 2.为什么需要会话?-http 协议是无状态的(六亲不认)-同一用户多次访问同一网站,对网站来说,每次都是全新的-网站不能识别用户身份…...
Java测试——junit的使用(2)
排序 我们同一个类下的多个用例的执行顺序是不确定的,如果需要指定固定的顺序,则需要在类上加这个注解 TestMethodOrder(MethodOrderer.OrderAnnotation.class)然后在想要第一个执行的用例上加上 Order(1)第二个执行的用例上注解: Order(…...
数据库(六): MySQL的主从复制和读写分离
文章目录一、为什么要使用主从复制和读写分离二、主从复制的原理三、如何实现主从复制3.1 master配置3.2 slave配置3.3 测试主从复制四、读写分离五、缺点一、为什么要使用主从复制和读写分离 注意到主从复制和读写分离一般是一起使用的。目的很简单,就是提高数据库…...
编程思想-0x00架构
产生架构的原因? 1、代码均摊 将不同的代码进行分块,然后简历联系,低耦合、高内聚; 原则上:合理的App架构应该是合理分配每个类、结构体、方法、变量的存在都应该遵循单一职责的原则 2、便于测试 测试确保代码质量&…...
QCon演讲实录(上):多云环境下应用管理与交付实践
作者:阿里云大数据基础工程技术团队——郭耀星 大家上午好!我是来自阿里云大数据基础工程技术团队的郭耀星,花名雪尧。今天我很高兴能够来到QCon,与大家分享我的经验和心得。在当前的多云环境中,作为运维支撑团队&…...
async thunk 解决 API 调用的依赖问题
async thunk 解决 API 调用的依赖问题 一句话节省看下面一堆内容的时间就是: async thunk 中可以使用 async/await 锁住其他的 action 操作 一般 API 之间存在三种情况: A 和 B 之间没有依赖关系 这样的情况下,A 和 B 可以各调用各的&#x…...
java 黑马头条 day3 实名认证分布式事务问题 seata
1 完善实名认证功能 1.1 实名认证分布式事务问题 1.1.1 问题分析 在昨天的实名认证代码中,审核完毕后添加 id5的演示异常,重新使用postman进行测试, 会发现 出现异常后 本地方法因为有 Transactional注解 对ap_user ap_user_realname的操作会回滚 而…...
测试开发之Django实战示例 第七章 创建电商网站
第七章 创建电商网站在上一章里,创建了用户关注系统和行为流应用,还学习了使用Django的信号功能与使用Redis数据库存储图片浏览次数和排名。这一章将学习如何创建一个基础的电商网站。本章将学习创建商品品类目录,通过session实现购物车功能。…...
【C++之容器篇】造轮子:list的模拟实现与使用
目录前言一、关于list1. 简介2. 成员类型二、默认成员函数1. 构造函数1. list()2. list(size_t n,const T& val T())和list(InputIterator first,InputIterator last)2. 拷贝构造函数3. 析构函数4. 赋值运算符重载函数三、迭代器1. 普通对象的正向迭代器2. const对象的正向…...
自动驾驶:决策规划算法岗位面经分享
本专栏分享 计算机小伙伴秋招春招找工作的面试经验和面试的详情知识点 专栏首页: 主要分享计算机算法类在面试互联网公司时候一些真实的经验 人情况是985本硕,硕士研究方向是强化学习在移动机器人路径规划中的应用,一段自动驾驶中小厂实习经历,秋招找的大都是机器人和自动驾…...
2.7、进程调度的时机、切换与过程、方式
1、进程调度的时机 进程调度\color{red}进程调度进程调度(低级调度),就是按照某种算法从就绪队列中选择一个进程为其分配处理机 进程在操作系统内核程序临界区\color{red}操作系统内核程序临界区操作系统内核程序临界区中不能\color{red}不能…...
工程管理系统源码+项目说明+功能描述+前后端分离 + 二次开发
工程项目各模块及其功能点清单 一、系统管理 1、数据字典:实现对数据字典标签的增删改查操作 2、编码管理:实现对系统编码的增删改查操作 3、用户管理:管理和查看用户角色 4、菜单管理:实现对系统菜单的增删改查操…...
ESP32S3系列--SPI从机驱动详解(一)
一、目的 在之前的博文中《ESP32S3系列--SPI主机驱动详解(一)》、《ESP32S3系列--SPI主机驱动详解(二)》我们详细讲解了ESP32S3上的SPI外设如何工作在主机模式并通过代码的形式帮助大家理解。 本篇我们将介绍SPI外设工作在从机模式下的使用知识点。 二、介绍 参考资料 http…...
【实战篇】移动端H5网页在ios滑动不流畅和禁止缩放问题
问题描述:移动端H5网页在ios滑动不流畅和禁止缩放问题 最近开发小程序,有一个富文本展示页面使用的是<webview>H5网页嵌入的,当你用 overflow-y:scroll 属性的时候,内容超出容器溢出滚动的效果很迟顿,特别是在IOS系统中,而且页面还会缩放。 解决方案: 1…...
ViGEmBus虚拟手柄驱动:Windows系统控制器仿真解决方案与开发者指南
ViGEmBus虚拟手柄驱动:Windows系统控制器仿真解决方案与开发者指南 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 核心价值解析:重新…...
3个实战场景:League-Toolkit如何帮你提升英雄联盟游戏体验
3个实战场景:League-Toolkit如何帮你提升英雄联盟游戏体验 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾在…...
Windows右键菜单管理效率提升指南:用ContextMenuManager打造个性化定制体验
Windows右键菜单管理效率提升指南:用ContextMenuManager打造个性化定制体验 【免费下载链接】ContextMenuManager 🖱️ 纯粹的Windows右键菜单管理程序 项目地址: https://gitcode.com/gh_mirrors/co/ContextMenuManager 你是否曾遇到这样的场景&…...
5款Umi-OCR插件全解析:让文字识别效率提升300%的实用指南
5款Umi-OCR插件全解析:让文字识别效率提升300%的实用指南 【免费下载链接】Umi-OCR_plugins Umi-OCR 插件库 项目地址: https://gitcode.com/gh_mirrors/um/Umi-OCR_plugins 为什么你的文字识别总是效率低下? 还在为图片转文字耗时过长而抓狂&am…...
告别本地局限!OpenClaw从本地监听改公网监听,手把手实操教程
💡 前言 在部署OpenClaw的过程中,很多小伙伴都会遇到一个共性问题:服务默认仅监听本地回环地址([127.0.0.1](127.0.0.1)),只能在服务器本机访问,完全没法满足远程管理、跨设备调用、公网服务暴露的实际业务需求。想要让OpenClaw真正发挥作用,核心就是把监听模式从本地…...
FLUX小红书V2模型版本对比:V1与V2的核心改进与效果差异
FLUX小红书V2模型版本对比:V1与V2的核心改进与效果差异 1. 引言 如果你最近在玩AI图像生成,特别是想做出那种看起来特别真实、特别有小红书风格的照片,那你肯定听说过FLUX小红书模型。这个模型从V1版本开始就挺火的,主要是因为它…...
RWKV7-1.5B-g1a入门必看:轻量中文问答/文案续写/摘要生成快速上手指南
RWKV7-1.5B-g1a入门必看:轻量中文问答/文案续写/摘要生成快速上手指南 1. 模型简介 RWKV7-1.5B-g1a是一个基于RWKV-7架构的多语言文本生成模型,特别适合中文场景下的基础问答、文案续写、简短总结和轻量对话任务。这个1.5B参数的版本在保持良好生成质量…...
Nacos如何开启ssl(https)[图文版]
首先,你得有个域名,只有域名才能有ssl 在你的腾讯云或者阿里云控制台把域名解析到nacos所在的ip上面 等待几分钟,打开cmd, ping 刚才的域名,如果返回的是nacos的ip那说明解析成功了 例如你的域名是 ttvv.com 那就 ping ttvv.com 准备证书文件 你的证书通常是 .pem 和 .key …...
SkeyeVSS中国标GB28181、流媒体源RTMP/RTSP/HTTP/ONVIF、RTMP推流等协议视频流实时播放流程详解
本文基于 core/app/sev/vss/internal/logic/http/video/stream_play.go 的源码:从参数与设备查询,到按接入协议分支、触发 MS 拉流或 GB28181 Invite,再到返回 StreamResp 与异步处理。 源码地址 点击直达 一、接口入口与请求体 项目说明…...
Matlab图表标注全攻略:希腊字母、线型与标记符号的灵活运用
Matlab图表标注全攻略:希腊字母、线型与标记符号的灵活运用 科研图表是数据可视化的核心载体,而Matlab作为工程与科学计算领域的标杆工具,其绘图系统的精细控制能力往往被低估。许多研究者止步于默认图表样式,却不知只需掌握几个关…...
