1021. 删除最外层的括号
2023-02-18 16:34:56 时间
1021. 删除最外层的括号
有效括号字符串为空 ("")、"(" + A + ")" 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,"","()","(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。
示例 1:
输入:"(()())(())"
输出:"()()()"
解释:
输入字符串为 "(()())(())",原语化分解得到 "(()())" + "(())",
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2:
输入:"(()())(())(()(()))"
输出:"()()()()(())"
解释:
输入字符串为 "(()())(())(()(()))",原语化分解得到 "(()())" + "(())" + "(()(()))",
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3:
输入:"()()"
输出:""
解释:
输入字符串为 "()()",原语化分解得到 "()" + "()",
删除每个部分中的最外层括号后得到 "" + "" = ""。
代码1:
string removeOuterParentheses(string S) {
string res, tmp;
int sum = 0;
for (int i = 0; i < S.size(); i++){
tmp += S[i];
if (S[i] == '(')
sum++;
else
sum--;
if (sum == 0){
res.append(tmp.begin() + 1, tmp.end() - 1);
tmp = "";
}
}
return res;
}
代码2:
string removeOuterParentheses(string S) {
int L=1;int R=0;
string ans;
for(int i=1;i<S.size();i++){
if(S[i]=='(')L++;
else R++;
if(R!=L)ans.push_back(S[i]);
else {
i++;L=1;R=0;
}
}
return ans;
}
代码3:
void del(){
deque<char>dq;
deque<char>::iterator itpre,it;
string str;
cin>>str;
int len =str.length();
int lcount=0,rcount=0,count=0;
for (int i = 0; i < len; i++)
{
if (lcount==0&&rcount==0)
{
itpre = dq.begin()+i-count;
count++;
}
if (str[i]=='(')
{
lcount++;
dq.push_back('(');
}else if(str[i]==')')
{
rcount++;
dq.push_back(')');
}
if (lcount==rcount)
{
dq.erase(itpre);
dq.pop_back();
lcount =rcount =0;
}
}
for (it = dq.begin(); it!=dq.end(); it++)
{
cout<<*it<<"";
}
}
相关文章
- Netflix Eureka 2.0.0正式发布:借尸还魂还是虚晃一枪?
- Redis数据结构存储系统:第三章:Redis在项目中如何使用?
- [TMLR | 论文简读] GemNet-OC:开发用于大型和多样化的分子模拟数据集的图神经网络
- [nature genetics | 论文简读] 用序列模型从染色体角度来预测3D基因组结构
- 利用 Kruise Rollouts 对 Kubernetes 资源实现金丝雀发布
- Kubernetes 的 CI/CD 管道概述
- ChatGPT初体验|在 ChatGPT 中运行容器或Kubernetes?
- [Briefings in Bioinformatics|论文简读]NetTDP:基于互换的真实发现比例的差异性共表达网络分析
- [IEEE Trans Med Imaging | 论文简读] Av-CasNet:OCT血管成像中的微血管全自动分割与区分
- [Information Sciences | 论文简读] DA-Net:用于多变量时间序列分类的双注意力网络
- 如何验证Kubernetes YAML Files
- 利用php脚本+redis,生成CSV测试文件,重复率为20%
- [MySQL]索引
- [MySQL]brew 安装 配置 操作 mysql(中文问题)
- [MySQl]MySQL忘记密码
- [MySQL]增加用户 授权 远程登录
- [编程题目]泥塑课
- How can I learn to program?
- 学渣的心酸(求职篇)
- 时间复杂度问题