分割平衡字符串
2023-02-18 16:34:53 时间
在一个「平衡字符串」中,'L' 和 'R' 字符的数量是相同的。给出一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。
示例 1:
输入:s = "RLRRLLRLRL"
输出:4
解释:s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 2:
输入:s = "RLLLLRRRLR"
输出:3
解释:s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
示例 3:
输入:s = "LLLLRRRR"
输出:1
解释:s 只能保持原样 "LLLLRRRR".
思路1:
通过计数L 与R 的个数,判断什么时候最早两者相等,即为最短子串。
代码1:
#include<iostream>
#include<cstring>
using namespace std;
int main(){
string str;
cin>>str;
int Lpos,Rpos,Lcount,Rcount,total=0;
Lpos=Rpos=Lcount=Rcount=0;
int len=str.length();
for (int i = 0; i < len; i++)
{
if(Lcount==0&&Rcount==0) Lpos=i;//重新开始找
if (str[i]=='L')//记录L 的个数
{
Lcount++;
}else if (str[i]=='R') //记录R的个数
{
Rcount++;
}
if (Lcount==Rcount)//找到L ==R 的子串
{
Rpos=i;
Lcount=Rcount=0;
total++;
// cout<<str.substr(Lpos,i-Lpos+1)<<endl;
}
}
cout<<total<<endl;
}
思路2:前缀和
把L看作1,R看作-1,构建前缀和,当前缀和为0时,说明LR个数相等
返回前缀和中0的个数
代码2:
int balancedStringSplit() {
string s;
cin>>s;
int sum=0,cnt=0;
for(int i=0;s[i];i++)
{
char a =s[i];
if(a=='R') ++cnt;
if(a=='L') --cnt;
if(cnt==0) ++sum;
}
return sum;
}
相关文章
- H3C路由交换 Smart Link & Monitor Link
- 在 C# 9 中使用 foreach 扩展
- 如何实现隐式类型转换
- 如何指定多个项目的 InternalsVisibleTo
- 如何在多个应用程序中共享日志配置
- 为 ASPNETCORE 7 项目添加 Serilog
- 如何在路由绑定中使用 IParsable
- 如何使用 EF Core 7 批量删除数据
- 如何在 .Net 7 中将 Query 绑定到数组
- 实现 .Net 7 下的数据库定时检查
- 使用 BenchmarkDotNet 比较指定容量的 List 的性能
- 如何使用 IdGen 生成 UID
- 通过 CancellationToken 提高 Web 性能
- 为什么总是应该考虑给定 List 的初始大小
- 为什么 Random.Shared 是线程安全的
- 乡亲们,我们创建了 Dapr 中文交流频道
- oh,我的老伙计,你看看这近五十个dapr视频
- 字符串池化,减少了三分之一的内存占用
- 简单三分钟,本地搭建 k8s
- 基于 Blazor 打造一款实时字幕