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

leetcode每日一题:替换子串得到平衡字符串

引言

今天的每日一题原题是1863. 找出所有子集的异或总和再求和,比较水,直接对于集合中的每一个元素,都有取或者不取2种情况,直接递归进去求和即可。更换成前几天遇到的更有意思的一题来写这个每日一题。

题目

有一个只含有 '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 <= 10^5

  • s.length4 的倍数

  • s 中只含有 'Q', 'W', 'E', 'R' 四种字符

思路

        可以利用滑动窗口的思想来解题,由于替换进去的字符串内容是任意的,所以只要满足选取1个字符串后,剩下的4个字符的个数都小于等于 length / 4 即可。

        可以先存下起始时每个字符的个数,如果当前就满足平衡条件,那么直接返回0即可。如果当前不平衡,我们尝试从0到length枚举替换字符的左端点,然后右端点不断向右滑动,这样在滑动的过程中,最右边位置的字符个数-1,直到剩余字符满足小于等于 length / 4 或者到达原始字符串边界。注意这里要再判断1次是否满足平衡条件,因为可能是因为到达原始边界才退出的。当滑动到某位置可以满足平衡的时候,r - l就是我们要替换的字符串长度。最后,枚举下1组左端点的时候,又相当于最左边位置的字符放回原始数组中,所以不要忘记操作charNum[getIndex1234(chars[l])]++

         另外吐槽一下,这里QWER在字母表并不连续,只能写了一个映射的方法来映射到下标0~3,否则就要开更大的数组来存,比如26。

代码

class Solution {public int balancedString(String s) {int[] charNum = new int[4];char[] chars = s.toCharArray();for (char c : chars) {charNum[getIndex1234(c)]++;}int ans = s.length();int stand = ans / 4;if (charNum[0] == stand && charNum[1] == stand && charNum[2] == stand) {// 判断3个就够了,3个都是stand,最后1个一定是standreturn 0;}for (int l = 0, r = 0; l < s.length(); l++) {while (r < s.length() && !check(charNum, stand)) {// 右边向右滑动1位,最右边位置的字符个数-1charNum[getIndex1234(chars[r])]--;r++;}if (!check(charNum, stand)) {break;}ans = Integer.min(ans, r - l);// 左边向右滑动1位,最左边位置的字符个数+1charNum[getIndex1234(chars[l])]++;}return ans;}
​/*** QWER 返回下标* @param c* @return*/private static int getIndex1234(char c) {int index = -1;switch (c) {case 'Q':index = 0;break;case 'W':index = 1;break;case 'E':index = 2;break;case 'R':index = 3;break;}return index;}
​private static boolean check(int[] charNum, int stand) {return charNum[0] <= stand && charNum[1] <= stand && charNum[2] <= stand && charNum[3] <= stand;}
}
耗时

相关文章:

leetcode每日一题:替换子串得到平衡字符串

引言 今天的每日一题原题是1863. 找出所有子集的异或总和再求和&#xff0c;比较水&#xff0c;直接对于集合中的每一个元素&#xff0c;都有取或者不取2种情况&#xff0c;直接递归进去求和即可。更换成前几天遇到的更有意思的一题来写这个每日一题。 题目 有一个只含有 Q,…...

2025年数字化社会与智能计算国际学术会议 (ICDSIC 2025)

基本信息 官网&#xff1a;www.icdsic.net 时间&#xff1a;2025年4月18-20日 地点&#xff1a;中国-深圳 主题 数字化社会 智能计算 数字化制造、经济 数字化政务、转型 数字化农业、水利、管理 数字化医疗、学习、社区 数字基建、通信、交通 数字…...

BN测试和训练时有什么不同, 在测试时怎么使用?

我们来彻底搞懂 Batch Normalization&#xff08;BN&#xff09; 在训练和测试阶段的区别&#xff0c;以及 测试时怎么用。 &#x1f9e0; 一句话总结&#xff1a; 训练时&#xff1a;使用 当前 mini-batch 的均值和方差 测试时&#xff1a;使用 整个训练集估计的“滑动平均均值…...

为什么卷积神经网络适用于图像和视频?

我们常听说“卷积神经网络&#xff08;CNN&#xff09;擅长图像和视频”&#xff0c;但其实 CNN 的核心本质远不止图像领域。我们先搞懂它为啥适合图像/视频。 &#x1f9e0;CNN 为什么适用于图像和视频&#xff1f; 主要因为 图像/视频具有空间局部性和结构平移性&#xff0c…...

python爬虫:DrissionPage实战教程

如果本文章看不懂可以看看上一篇文章&#xff0c;加强自己的基础&#xff1a;爬虫自动化工具&#xff1a;DrissionPage-CSDN博客 案例解析&#xff1a; 前提&#xff1a;我们以ChromiumPage为主&#xff0c;写代码工具使用Pycharm&#xff08;python环境3.9-3.10&#xff09; …...

【Python爬虫高级技巧】BeautifulSoup高级教程:数据抓取、性能调优、反爬策略,全方位提升爬虫技能!

大家好&#xff0c;我是唐叔&#xff01;上期我们聊了 BeautifulSoup的基础用法 &#xff0c;今天带来进阶篇。我将分享爬虫老司机总结的BeautifulSoup高阶技巧&#xff0c;以及那些官方文档里不会告诉你的实战经验&#xff01; 文章目录 一、BeautifulSoup性能优化技巧1. 解析…...

【动手学深度学习】卷积神经网络(CNN)入门

【动手学深度学习】卷积神经网络&#xff08;CNN&#xff09;入门 1&#xff0c;卷积神经网络简介2&#xff0c;卷积层2.1&#xff0c;互相关运算原理2.2&#xff0c;互相关运算实现2.3&#xff0c;实现卷积层 3&#xff0c;卷积层的简单应用&#xff1a;边缘检测3.1&#xff0…...

IPSG 功能协议

IPSG&#xff08;IP Source Guard&#xff09;即 IP 源保护&#xff0c;是一种基于 IP 地址和 MAC 地址绑定的安全功能&#xff0c;用于防止 IP 地址欺骗和非法的 IP 地址访问。以下是配置 IPSG 功能的一般步骤&#xff1a; 基于端口的 IPSG 配置 进入接口配置模式&#xff1…...

19.go日志包log

核心功能与接口 基础日志输出 Print 系列&#xff1a;支持 Print()、Println()、Printf()&#xff0c;输出日志不中断程序。 log.Print("常规日志") // 输出: 2025/03/18 14:47:13 常规日志 log.Printf("格式化: %s", "数据") Fatal…...

横扫SQL面试——TopN问题

横扫SQL面试 电商平台的"销量Top10商品"&#x1f6cd;️&#xff0c;内容社区的"热度Top5文章“”&#x1f525;&#xff0c;还是金融领域的"交易额Top3客户"&#x1f4b0;——TopN问题无处不在&#xff01; 无论是日常业务分析&#x1f4ca;&#x…...

高级:微服务架构面试题全攻略

一、引言 在现代软件开发中&#xff0c;微服务架构被广泛应用于构建复杂、可扩展的应用程序。面试官通过相关问题&#xff0c;考察候选人对微服务架构的理解、拆分原则的掌握、服务治理的能力以及API网关的运用等。本文将深入剖析微服务架构相关的面试题&#xff0c;结合实际开…...

使用MATIO库读取Matlab数据文件中的cell结构数据

使用MATIO库读取Matlab数据文件中的cell结构数据 MATIO是一个用于读写Matlab数据文件(.mat)的C/C库。下面我将展示如何使用MATIO库来读取Matlab文件中的cell结构数据。 示例程序 #include <stdio.h> #include <stdlib.h> #include <matio.h>int main(int …...

pyTorch框架使用CNN进行手写数字识别

目录 1.导包 2.torchvision数据处理的方法 3.下载加载手写数字的训练数据集 4.下载加载手写数字的测试数据集 5. 将训练数据与测试数据 转换成dataloader 6.转成迭代器取数据 7.创建模型 8. 把model拷到GPU上面去 9. 定义损失函数 10. 定义优化器 11. 定义训练…...

新能源汽车电子电气架构设计中的功能安全

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 周末洗了一个澡,换了一身衣服,出了门却不知道去哪儿,不知道去找谁,漫无目的走着,大概这就是成年人最深的孤独吧! 旧人不知我近况,新人不知我过…...

使用binance-connector库获取Binance全市场的币种价格,然后选择一个币种进行下单

一个完整的示例,展示如何使用 api 获取Binance全市场的币种价格,然后选择一个最便宜的币种进行下单操作 代码经过修改,亲测可用,目前只可用于现货,合约的待开发 获取市场价格:使用client.ticker_price()获取所有交易对的当前价格 账户检查:获取账户余额,确保有足够的资…...

HikariCP 源码核心设计解析与 ZKmall开源商城场景调优实践

HikariCP 作为 Spring Boot 默认数据库连接池&#xff0c;其高性能源于独特的无锁设计、轻量级数据结构和精细化生命周期管理。以下从源码解析与 ZKmall开源商城性能调优两个维度展开&#xff1a; 一、HikariCP 源码核心设计解析 ​无锁并发控制与 ConcurrentBag 容器 ​Concur…...

P1036 [NOIP 2002 普及组] 选数(DFS)

题目描述 已知 n 个整数 x1​,x2​,⋯,xn​&#xff0c;以及 1 个整数 k&#xff08;k<n&#xff09;。从 n 个整数中任选 k 个整数相加&#xff0c;可分别得到一系列的和。例如当 n4&#xff0c;k3&#xff0c;4 个整数分别为 3,7,12,19 时&#xff0c;可得全部的组合与它…...

自然语言处理

自然语言处理基础 什么是自然语言处理&#xff1a;让计算机来理解人类所说的一种语言。自然语言处理实际就是让计算机理解人类说的话&#xff0c;然后像人一样进行交互&#xff0c;去进行对话&#xff0c;去生成自然语言。 自然语言处理的基本任务 词性标注&#xff1a;把给…...

LeetCode刷题常见的Java排序

1. 字符串排序(字母排序) 首先,你的代码实现了根据字母表顺序对字符串中的字母进行排序,忽略了大小写并且保留了非字母字符的位置。关键点是: 提取和排序字母:通过 Character.isLetter() 判断是否为字母,并利用 Character.toLowerCase() 来忽略大小写进行排序。保留非字…...

# 利用OpenCV和Dlib实现疲劳检测:守护安全与专注

利用OpenCV和Dlib实现疲劳检测&#xff1a;守护安全与专注 在当今快节奏的生活中&#xff0c;疲劳和注意力不集中是许多人面临的常见问题&#xff0c;尤其是在驾驶、学习等需要高度集中精力的场景中。疲劳不仅影响个人的健康和安全&#xff0c;还可能导致严重的事故。为了应对…...

python基础-16-处理csv文件和json数据

文章目录 【README】【16】处理csv文件和json数据【16.1】csv模块【16.1.1】reader对象【16.1.2】在for循环中&#xff0c; 从reader对象读取数据【16.1.3】writer对象【16.1.5】DictReader与DictWriter对象 【16.4】json模块【16.4.1】使用loads()函数读取json字符串并转为jso…...

Mysql 数据库编程技术01

一、数据库基础 1.1 认识数据库 为什么学习数据库 瞬时数据&#xff1a;比如内存中的数据&#xff0c;是不能永久保存的。持久化数据&#xff1a;比如持久化至数据库中或者文档中&#xff0c;能够长久保存。 数据库是“按照数据结构来组织、存储和管理数据的仓库”。是一个长…...

基于SSM的车辆管理系统的设计与实现(代码+数据库+LW)

摘要 当下&#xff0c;正处于信息化的时代&#xff0c;许多行业顺应时代的变化&#xff0c;结合使用计算机技术向数字化、信息化建设迈进。以前企业对于车辆信息的管理和控制&#xff0c;采用人工登记的方式保存相关数据&#xff0c;这种以人力为主的管理模式已然落后。本人结…...

BugKu Simple_SSTI_2

这个题很简单&#xff0c;主要是记录一下&#xff0c;做题的原理&#xff1a; 打开环境&#xff0c;提示我们用flag传参&#xff0c;然后我们需要判断是什么模板&#xff1a; 这里有一张图片&#xff0c;可以帮助我们轻松判断是什么模板类型&#xff1a;这个图片找不到出处了&…...

浙考!【触发器逻辑方程推导(电位运算)】

RS触发器是浙江高考通用技术一大考点。“对角线原则”、“置1置0”、“保持”、“不使用”、“记忆功能”…经常让考生云里雾里&#xff0c;非常反直觉。 这篇文章&#xff0c;我想以高中生的视角诠释一下触发器。 1、触发器逻辑方程推导&#xff08;以或非门触发器为例&…...

二叉树的前序中序后序遍历

一、前序遍历 144. Binary Tree Preorder Traversal 递归代码实现&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* …...

es中节点类型有哪些

Elasticsearch 节点类型有哪些 在 Elasticsearch 中&#xff0c;节点类型&#xff08;或角色&#xff09;定义了每个节点在集群中的职责。不同版本的 Elasticsearch 对节点角色的定义和管理方式有所不同&#xff0c;尤其在 7.9.0 版本引入 node.roles 后&#xff0c;配置方式更…...

【学习笔记】深度学习环境部署相关

文章目录 [AI硬件科普] 内存/显存带宽&#xff0c;从 NVIDIA 到苹果 M4[工具使用] tmux 会话管理及会话持久性[A100 02] GPU 服务器压力测试&#xff0c;gpu burn&#xff0c;cpu burn&#xff0c;cuda samples[A100 01] A100 服务器开箱&#xff0c;超微平台&#xff0c;gpu、…...

游戏引擎学习第206天

回顾并为当天的工作定下目标 接着回顾了前一天的进展。之前我们做了一些调试功能&#xff0c;并且已经完成了一些基础的工作&#xff0c;但是还有一些功能需要继续完善。其中一个目标是能够展示实体数据&#xff0c;以便在开发游戏逻辑系统时&#xff0c;可以清晰地查看和检查…...

Rust所有权详解

文章目录 Rust所有权所有权规则作用域 内存和分配移动与克隆栈空间堆空间 关于函数的所有权机制作为参数作为返回值 引用与租借垂悬引用 Rust所有权 C/C中我们对于堆内存通常需要自己手动管理&#xff0c;手动申请和释放&#xff0c;即便有了智能指针&#xff0c;对于效率的影…...

贪心算法的使用条件

1. 算法原理 贪心算法是一种在每一步选择中都采取当前状态下最优&#xff08;局部最优&#xff09;的策略&#xff0c;从而希望最终得到全局最优解的算法。其核心思想是&#xff1a;“目光短浅” 地选择当前最优解&#xff0c;不回溯、不瞻前顾后。 示例&#xff1a;活动选择问…...

网络性能优化参数关系解读 | TCP Nagle / TCP_NODELAY / TCP_QUICKACK / TCP_CORK

注&#xff1a;本文为 “网路性能优化” 相关文章合辑。 未整理去重。 如有内容异常&#xff0c;请看原文。 TCP_NODELAY 详解 lenky0401 发表于 2012-08-25 16:40 在网络拥塞控制领域&#xff0c;Nagle 算法&#xff08;Nagle algorithm&#xff09;是一个非常著名的算法&…...

《打破SQL与AI框架对接壁垒,解锁融合新路径》

在当今科技飞速发展的浪潮中&#xff0c;SQL作为管理和处理关系型数据的经典语言&#xff0c;与代表前沿技术的人工智能框架之间的融合&#xff0c;正逐渐成为推动数据驱动型应用发展的重要力量。这种融合所带来的接口实现&#xff0c;不仅是技术上的突破&#xff0c;更是为众多…...

虚拟Ashx页面,在WEB.CONFIG中不添加handlers如何运行

https://localhost:44311/webapi.ashx 虚拟ASHX页面,在WEB.CONFIG中添加handlers&#xff0c;如何不添加节点&#xff0c;直接运行?把页面直接保存ASHX名称&#xff1f;现在是.VB 如果你不想通过在 web.config 里添加 handlers 节点来配置处理程序&#xff0c;而是直接让 .as…...

【ssrf漏洞waf绕过】

SSRF绕过方法 SSRF对于防御方式(waf)绕过方法 SSRF攻击内网的redis 题目一 基于java 的一个 WEBLOGIC 框架 首先我们要知道它内网有什么服务&#xff0c;我们正常给8888端口发送请求是能接受到的&#xff0c;那么我们把8888端口给关闭了&#xff0c;再次请求发现后有一个错误…...

BEVFormer v2(CVPR2023)

文章目录 AbstractIntroductionRelated WorksBEV 3D Object DetectorAuxiliary Loss in Camera 3D Object DetectionTwo-stage 3D Object Detector BEVFormer v2Overall ArchitecturePerspective SupervisionPerspective LossRavamped Temporal EncoderTwo-stage BEV DetectorD…...

车载通信架构 --- AUTOSAR 网络管理

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 周末洗了一个澡,换了一身衣服,出了门却不知道去哪儿,不知道去找谁,漫无目的走着,大概这就是成年人最深的孤独吧! 旧人不知我近况,新人不知我过…...

STM32单片机入门学习——第16节: [6-4] PWM驱动LED呼吸灯PWM驱动舵机PWM驱动直流电机

写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难&#xff0c;但我还是想去做&#xff01; 本文写于&#xff1a;2025.04.05 STM32开发板学习——第16节: [6-4] PWM驱动LED呼吸灯&PWM驱动舵机&PWM驱…...

RoMo: Robust Motion Segmentation Improves Structure from Motion

前言 看起来像是一篇投稿CVPR的文章&#xff0c;不知道被哪个瞎眼审稿人拒了。同期还有一篇CVPR被接收的工作Segment Any Motion in Videos&#xff0c;看起来不如这篇直白&#xff08;也可能是因为我先看过spotlesssplats的缘故&#xff09;&#xff0c;后面也应该一并介绍了…...

【AI编程学习之Python】第五天:Python的变量和常量

对象 Python中一切变量的值皆为对象。每个对象由:标识(identity)、类型(type)、value(值)组成。 标识用于唯一标识对象,通常对应于对象在计算机内存中的地址。使用内置函数id(obj)可返回对象obj的标识。 类型用于表示对象存储的“数据”的类型。类型可以限制对象的取值范围以…...

经典算法 约数之和

原题目链接 问题描述 假设现在有两个自然数 A 和 B&#xff0c;设 S 为 A^B 的所有约数之和。 请你计算&#xff1a;S mod 9901 的值。 输入格式 在一行中输入两个用空格隔开的整数 A 和 B。 输出格式 输出一个整数&#xff0c;表示 S mod 9901 的值。 数据范围 0 ≤ A, …...

zookeeper基本概念和核心作用

图片来源&#xff1a; 02-Zookeeper概念_哔哩哔哩_bilibili02-Zookeeper概念是黑马程序员Zookeeper视频教程&#xff0c;快速入门zookeeper技术的第2集视频&#xff0c;该合集共计24集&#xff0c;视频收藏或关注UP主&#xff0c;及时了解更多相关视频内容。https://www.bilib…...

蓝桥杯嵌入式客观题二

十四届模拟一 1. 2.串口通信是一种传输线按位数据顺序传输方式 3.USART_SR是属于STM32微控制器USART的状态寄存器。 4.STM32G431RBT6是32位的ARM微控制器 ARM处理器是英国ARM公司设计的一种低功耗RISC微处理器 5.中断配置‌EXTI->FTSR&#xff08;下降沿触发选择寄存器…...

第一章:服务架构演进史_《凤凰架构:构建可靠的大型分布式系统》_Notes

第一章 服务架构演进史 1. 原始分布式时代&#xff08;1970s-1980s&#xff09; 核心问题&#xff1a;如何用不可靠的硬件构建可靠的大规模系统&#xff1f; 关键知识点&#xff1a; 技术背景&#xff1a; 硬件限制&#xff1a;微型计算机性能低下&#xff08;如Intel 8086处…...

BUUCTF-web刷题篇(13)

22.NiZhuanSiWei 分析&#xff1a;有三个参数需要以get方式传入&#xff0c;发现有file_get_contents()&#xff0c;所以要使用php伪代码&#xff0c;preg_match("/flag/",$file)说明正则匹配不能含有flag&#xff0c;同时还有反序列化&#xff0c;存在漏洞。 已知前…...

7-9 趣味游戏

题目解析 在某个学校的趣味游戏活动中&#xff0c;N 名同学站成一排&#xff0c;他们的年龄恰好是 1 到 N &#xff0c;需要注意的是他们并不是按照年龄的大小排列的&#xff0c;而是随机排列的。 游戏的规则是请同学们快速计算出&#xff0c;如果在这 N 名同学的小组中&…...

用 Python 制作仓库自动化指南

1. 环境准备 Python 3.x pip (Python 包管理工具) 文本编辑器或 IDE (如 VS Code、PyCharm) 2. 安装依赖库 pandas: 数据处理 openpyxl: Excel 文件操作 sqlite3: SQLite 数据库交互 smtplib: 邮件发送 bash pip install pandas openpyxl sqlite3 smtplib 3. 功能实现…...

Johnson算法——两阶段流水线调度的最优解法

前言&#xff1a;写这个题目的时候感觉就是说任务a的时候是一定需要的&#xff0c;无法避免&#xff0c;怎么才能节约时间呢&#xff0c;就是进行任务a时候也进行任务b 第一个进行的任务a肯定时间越短越好&#xff0c;因为这样b的等待时间越短 最后一个进行的任务b的时候越短越…...

反向查询详解以Django为例

以下给出两张表格 class User(AbstractUser):mobilemodels.CharField(max_length11,default0,uniqueTrue,verbose_name手机号)email_activemodels.BooleanField(defaultFalse,verbose_name邮箱验证状态)default_address models.ForeignKey(Address, related_nameusers, nullT…...

PDP动物性格测试:趣味性格分析工具

PDP动物性格测试&#xff1a;趣味性格分析工具 &#x1f4dd; 简介 大家好&#xff01;今天我想向大家推荐一个有趣且实用的在线工具 —— PDP动物性格测试。这是一个基于PDP&#xff08;Process Dynamic Pattern&#xff09;理论的性格测试工具&#xff0c;通过将性格特征与…...