每日一题.1021.删除最外层的括号
删除 每日 括号
2023-09-27 14:26:29 时间
题目
有效括号字符串为空 ""、"(" + 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.栈
遍历 s,并用一个栈来表示括号的深度。遇到 第一个‘(’ 则将字符入栈,遇到 ‘)’ 则将栈顶字符出栈。栈从空到下一次空的过程,则是扫描了一个原语的过程。一个原语中,首字符和尾字符应该舍去,其他字符需放入结果字符串中。因此,在遇到 ‘(’ 并将字符入栈后,如果栈的深度为 1,则不把字符放入结果;在遇到 ‘)’ 并将栈顶字符出栈后,如果栈为空,则不把字符放入结果。其他情况下,需要把字符放入结果。代码对流程进行了部分优化,减少了判断语句。
2.计数
大体思路和上述差不多,只是不申请额外的空间,直接记录括号的个数,当正好为零是将当前位置忽视,不为零是存入
代码
/*
*removeOuterParentheses:对 s 进行原语化分解,删除分解中每个原语字符串的最外层括号
char * s:有效字括号符串
*/
char * removeOuterParentheses(char * s) {
int len = strlen(s);
char *res = (char *)malloc(sizeof(char) * len);
char *stack = (char *)malloc(sizeof(char) * (len / 2));
int pos = 0, top = 0;
for (int i = 0; i < len; i++) {
char c = s[i];
if (c == ')') {
top--;
}
if (top > 0) {
res[pos++] = c;
}
if (c == '(') {
stack[top++] = c;
}
}
free(stack);
res[pos] = '\0';
return res;
}
方法二
/*
*removeOuterParentheses:对 s 进行原语化分解,删除分解中每个原语字符串的最外层括号
char * s:有效字括号符串
*/
char * removeOuterParentheses(char * s) {
int len = strlen(s);
char * ans = malloc(sizeof(char)*(len + 1));
int m = 0,n = 0;
int i = 0;
char c;
for(i = 0; i < len; i++)
{
if(s[i] == ')')
{
n++;
}
if(n)
{
ans[m++] = s[i];
}
if(s[i] == '(')
{
n--;
}
}
ans[m] = '\0';
return ans;
}
相关文章
- Linux删除以减号开头的文件
- 表单多文件上传样式美化 && 支持选中文件后删除相关项
- ASP.NET MVC对WebAPI接口操作(添加,更新和删除)
- python 删除前3天的文件
- SharePoint 删除废弃站点步骤
- odoo伪删除
- [转载]C++STL—vector的插入与删除
- 删除/添加/调用WordPress用户个人资料的联系信息
- php 创建删除数据库
- 链表的插入、删除和查询—C语言
- LeetCode·每日一题·1653. 使字符串平衡的最少删除次数·前缀和
- 中煜软件,数据库删除凭证
- 一次oracle大量数据删除经历
- anaconda创建和删除环境
- c#删除移动硬盘中$RECYCLE.BIN的文件、建立索引文件
- C++ 文件的复制、删除、重命名
- 在 CentOS 8 中删除旧的 Linux 系统内核