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

Leetcode.1234 替换子串得到平衡字符串

题目链接

Leetcode.1234 替换子串得到平衡字符串 Rating : 1878

题目描述

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

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

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

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

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

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

示例 1:

输入:s = “QWER”
输出:0
解释:s 已经是平衡的了。

示例 2:

输入:s = “QQWE”
输出:1
解释:我们需要把一个 ‘Q’ 替换成 ‘R’,这样得到的 “RQWE” (或 “QRWE”) 是平衡的。

示例 3:

输入:s = “QQQW”
输出:2
解释:我们可以把前面的 “QQ” 替换成 “ER”。

示例 4:

输入:s = “QQQQ”
输出:3
解释:我们可以替换后 3 个 ‘Q’,使 s = “QWER”。

提示:

  • 1<=s.length<=1051 <= s.length <= 10^51<=s.length<=105
  • s.length4的倍数
  • s中只含有 'Q', 'W', 'E', 'R'四种字符

分析:

s的长度为 n,那么每一个 'Q', 'W', 'E', 'R',的个数都应该是 m = n / 4

用两个指针 ij,维护一个 [i,j]的区间(滑动窗口),要替换的就是这个区间。除开这个区间的每一个字符的出现次数都 小于等于m的话,这个区间就可以替换。否则不可以。

时间复杂度:O(n)O(n)O(n)

代码:

class Solution {
public:int balancedString(string s) {int n = s.size();unordered_map<char,int> cnt;//先记录每个字符的出现次数for(auto c:s) cnt[c]++;int m = n / 4;//如果已经满足要求 就不需要替换if(cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m) return 0;int ans = n;for(int j = 0,i = 0;j < n;j++){cnt[s[j]]--;// [i,j] 这个区间就是需要替换的while(cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m){ans = min(ans,j-i+1);cnt[s[i++]]++;}}return ans;}
};

相关文章:

Leetcode.1234 替换子串得到平衡字符串

题目链接 Leetcode.1234 替换子串得到平衡字符串 Rating &#xff1a; 1878 题目描述 有一个只含有 Q, W, E, R四种字符&#xff0c;且长度为 n 的字符串。 假如在该字符串中&#xff0c;这四个字符都恰好出现 n/4次&#xff0c;那么它就是一个「平衡字符串」。 给你一个这样…...

聚类算法之K-means算法详解

文章目录 什么是聚类k-means算法简介牧师-村民模型算法步骤伪代码流程描述手动实现优缺点优点缺点算法调优与改进数据预处理合理选择 K 值手肘法Gap Statistic(间隔统计量)轮廓系数法(Silhouette Coefficient)Canopy算法拍脑袋法采用核函数K-means++ISODATA参考文献<...

电话呼入/呼出CSFB流程介绍

MO CSFB 注册的LAI跟SYS_INFO不同会触发LU流程;LU流程结束后,判断LOCATION UPDATING ACCEPT消息中的"Follow-on proceed"参数状态。(1)如果IE消息中有"Follow-on proceed",终端直接发送CM Service Request; (2)如果IE消息中没有"Follow-on procee…...

【比赛合集】9场可报名的「创新应用」、「程序设计」大奖赛,任君挑选!

CompHub 实时聚合多平台的数据类(Kaggle、天池…)和OJ类(Leetcode、牛客…&#xff09;比赛。本账号同时会推送最新的比赛消息&#xff0c;欢迎关注&#xff01;更多比赛信息见 CompHub主页 或 点击文末阅读原文以下信息仅供参考&#xff0c;以比赛官网为准目录创新应用赛&…...

剑指 Offer 27. 二叉树的镜像

剑指 Offer 27. 二叉树的镜像 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 请完成一个函数&#xff0c;输入一个二叉树&#xff0c;该函数输出它的镜像。 例如输入&#xff1a; 镜像输出&#xff1a; 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,…...

RPC编程:RPC概述和架构演变

RPC编程系列文章第一篇一&#xff1a;引言1&#xff1a;本系列文章的目标2&#xff1a;RPC的概念二&#xff1a;架构的演变过程1&#xff1a;单体架构1)&#xff1a;概念2)&#xff1a;特点3)&#xff1a;优缺点2&#xff1a;单体架构水平扩展1)&#xff1a;水平拓展的含义2)&a…...

神经网络训练时只对指定的边更新参数

在神经网络中&#xff0c;通常采用反向传播算法来计算网络中各个参数的梯度&#xff0c;从而进行参数更新。在反向传播过程中&#xff0c;所有的参数都会被更新。因此&#xff0c;如果想要只更新指定的边&#xff0c;需要采用特殊的方法。 一种可能的方法是使用掩码&#xff0…...

Python列表list操作-遍历、查找、增加、删除、修改、排序

在使用列表的时候需要用到很多方法&#xff0c;例如遍历列表、查找元素、增加元素、删除元素、改变元素、插入元素、列表排序、逆序列表等操作。 1、遍历列表 遍历列表通常采用for循环的方式以及for循环和enumerate&#xff08;&#xff09;函数搭配的方式去实现。 1&#xff…...

Python开发-学生管理系统

文章目录1、需求分析2、系统设计3、系统开发必备4、主函数设计5、 学生信息维护模块设计6、 查询/统计模块设计7、排序模块设计8、 项目打包1、需求分析 学生管理系统应具备的功能&#xff1a; ●添加学生及成绩信息 ●将学生信息保存到文件中 ●修改和删除学生信息 ●查询学生…...

大数据处理 - Trie树/数据库/倒排索引

Trie树Trie树的介绍和实现请参考 树 - 前缀树(Trie)适用范围: 数据量大&#xff0c;重复多&#xff0c;但是数据种类小可以放入内存基本原理及要点: 实现方式&#xff0c;节点孩子的表示方式扩展: 压缩实现。一些适用场景&#xff1a;寻找热门查询: 查询串的重复度比较高&#…...

jjava企业级开发-01

一、Spring容器演示 采用Spring配置文件管理Bean 1、创建Maven项目 修改项目的Maven配置 2、添加Spring依赖 在Maven仓库里查找Spring框架&#xff08;https://mvnrepository.com&#xff09; 同上添加其他依赖 <?xml version"1.0" encoding"UTF-8…...

「事务一致性」事务afterCommit

在事务还没有执行完消息就已经发出去了, 导致后续的一些数据或逻辑上的问题产生。场景如下&#xff1a;异步-记录日志&#xff1a;当事务提交后&#xff0c;再记录日志。发送mq消息&#xff1a;只有业务数据都存入表后&#xff0c;再发mq消息。方案1. 利用TransactionSynchroni…...

【深度学习编译器系列】2. 深度学习编译器的通用设计架构

在【深度学习编译器系列】1. 为什么需要深度学习编译器&#xff1f;中我们了解到了为什么需要深度学习编译器&#xff0c;和什么是深度学习编译器&#xff0c;接下来我们把深度学习编译器这个小黑盒打开&#xff0c;看看里面有什么东西。 1. 深度学习编译器的通用设计架构 与…...

图解操作系统

硬件结构 CPU是如何执行程序的&#xff1f; 图灵机的工作方式 图灵机的基本思想&#xff1a;用机器来模拟人们用纸笔进行数学运算的过程&#xff0c;还定义了由计算机的那些部分组成&#xff0c;程序又是如何执行的。 图灵机的基本组成如下&#xff1a; 有一条「纸带」&am…...

【发版或上线项目保姆级心得】

第一步&#xff1a;先在正式环境创建数据库/新增表格或者字段 在数据库表中增加字段/表格&#xff0c;不会报错。 但是切记不要过早数据库字段/表格或者删除字段/表格 第二步&#xff1a;修改配置文件 先将正式环境需要的配置给写好&#xff0c;包括但不仅限于数据库配置、…...

Python数据分析-pandas库入门

pandas 库概述pandas 提供了快速便捷处理结构化数据的大量数据结构和函数。自从2010年出现以来&#xff0c;它助使 Python 成为强大而高效的数据分析环境。pandas使用最多的数据结构对象是 DataFrame&#xff0c;它是一个面向列&#xff08;column-oriented&#xff09;的二维表…...

MacBook Pro 恢复出厂设置

目录1.恢复出厂设置1.1 按Command-R 键1.2 macOS 实用工具1.3 从 macOS 恢复功能的实用工具窗口中选择“磁盘工具”&#xff0c;然后点按“继续”1.4 在“磁盘工具”边栏中选择您的设备或宗卷。1.5 点按“抹掉”按钮或标签页1.6 抹掉OS X HD - 数据 完成1.7 抹掉 OS X HD1.8 查…...

googletest 笔记

什么是一个好的测试 1 测试应该是独立的和可重复的。调试一个由于其他测试而成功或 失败的测试是一件痛苦的事情。googletest 通过在不同的对象上 运行测试来隔离测试。当测试失败时&#xff0c;googletest 允许您单独运 行它以快速调试。 2 测试应该很好地“组织”&#xff0c…...

MySQL修改密码的几种方式?

第一种方式&#xff1a; 最简单的方法就是借助第三方工具Navicat for MySQL来修改。方法如下&#xff1a; 1、登录mysql到指定库&#xff0c;如&#xff1a;登录到test库。 2、然后点击上方"用户"按钮。 3、选择要更改的用户名&#xff0c;然后点击上方的"编辑用…...

关于画一个句号--基于2022年终总结的反思与分享

没有平台鼓风造势&#xff0c;今年各大平台没有涌现出一批总结&#xff0c;非常清爽 正如同人发明了抽屉&#xff0c;将杂物进行整理、丢弃、收纳&#xff0c;才能对空间进行更合理地使用。我们也需要对知识、过往经历进行整理、丢弃、收纳&#xff0c;才能对大脑进行更合理地…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...