每天算法刷题Day53:7.25:leetcode 栈5道题,用时1h35min
3. 1021. 删除最外层的括号(简单)
1021. 删除最外层的括号 - 力扣(LeetCode)
思想
1.有效括号字符串为空 ""
、"(" + A + ")"
或 A + B
,其中 A
和 B
都是有效的括号字符串,+
代表字符串的连接。
- 例如,
""
,"()"
,"(())()"
和"(()(()))"
都是有效的括号字符串。
如果有效字符串s
非空,且不存在将其拆分为s = A + B
的方法,我们称其为原语(primitive),其中A
和B
都是非空有效括号字符串。
给出一个非空有效字符串s
,考虑将其进行原语化分解,使得:s = P_1 + P_2 + ... + P_k
,其中P_i
是有效括号字符串原语。
对s
进行原语化分解,删除分解中每个原语字符串的最外层括号,返回s
。
2.简单来说就是从左向右不停地的获取满足左右括号完全匹配的原语,然后去掉最外层括号,放入答案中,可以利用分值有效性方法,左右括号完全匹配,即score=0
,记录最外层左括号括号的位置pre
,当前最外层右括号位置i
,然后把[pre+1,i)
插入到res
中即可
代码
class Solution {
public:string removeOuterParentheses(string s) {int n = s.size();int score = 0;string res;int pre = 0;for (int i = 0; i < n; ++i) {if (s[i] == '(')++score;else--score;if (score == 0) {// [pre+1,i)res.insert(res.end(), s.begin() + pre + 1, s.begin() + i);pre = i + 1;}}return res;}
};
4. 1614. 括号的最大嵌套深度(简单)
1614. 括号的最大嵌套深度 - 力扣(LeetCode)
思想
1.给定 有效括号字符串 s
,返回 s
的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。
2.嵌套深度即有效性分值score
的绝对值的最大值
代码
class Solution {
public:int maxDepth(string s) {int n = s.size();int res = 0;int score = 0;for (int i = 0; i < n; ++i) {if (s[i] == '(')++score;else if (s[i] == ')')--score;res = max(res, abs(score));}return res;}
};
5. 1190. 反转每对括号间的子串(中等)
1190. 反转每对括号间的子串 - 力扣(LeetCode)
思想
1.给出一个字符串 s
(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中 不应 包含任何括号。
2.因为括号具有对称性,所以想到先将这一层连同括号一起反转,所以要记录这一层左括号的下标,用栈维护,然后直接原地反转字符串s
,最后删除左右括号即可
代码
class Solution {
public:string reverseParentheses(string s) {int n = s.size();vector<int> stk;for (int i = 0; i < n; ++i) {if (s[i] == '(')stk.push_back(i);else if (s[i] == ')') {int pre = stk.back();// 反转[pre,i]reverse(s.begin() + pre, s.begin() + i + 1);stk.pop_back();}}s.erase(remove(s.begin(), s.end(), '('), s.end());s.erase(remove(s.begin(), s.end(), ')'), s.end());return s;}
};
6. 856. 括号的分数(中等,学习)
856. 括号的分数 - 力扣(LeetCode)
思想
1.给定一个平衡括号字符串 S
,按下述规则计算该字符串的分数:
()
得 1 分。AB
得A + B
分,其中 A 和 B 是平衡括号字符串。(A)
得2 * A
分,其中 A 是平衡括号字符串。
2.初始化将答案 0 放入栈中(后面逻辑决定的),从前往后处理整个 s,当遇到(
则存入一个占位数值 0,遇到)
取出栈顶元素 cur,根据栈顶元素数值分情况讨论:- 栈顶元素
cur=0
,即当前的)
的前一元素就是(
,根据()
得一分的规则可知,我们本次操作得到的分值为 1; - 栈顶元素
cur!=0
,即当前)
与其匹配的(
中间相隔了其他字符,根据(A)
的得分规则,此时可知得分为cur×2
;
将两者结合可统一为max(cur×2,1)
。
由于我们每次遇到)
时,都将最近一次操作计算出来。而再前面无论是)
还是(
我们都可以归结到X()
的相邻项累加规则,将其新得分累加到栈顶元素上,其中(
仍采用累加规则,则利用我们将(
定义为 0 的设定。
代码
class Solution {
public:int scoreOfParentheses(string s) {int n = s.size();vector<int> stk;stk.push_back(0);for (int i = 0; i < n; ++i) {if (s[i] == '(')stk.push_back(0);else {int cur = max(stk.back() * 2, 1);stk.pop_back();stk.back() += cur;}}return stk.back();}
};
7. 1249. 移除无效的括号(中等)
1249. 移除无效的括号 - 力扣(LeetCode)
思想
1.给你一个由 '('
、')'
和小写字母组成的字符串 s
。
你需要从字符串中删除最少数目的 '('
或者 ')'
(可以删除任意位置的括号),使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求:
- 空字符串或只包含小写字母的字符串
- 可以被写作
AB
(A
连接B
)的字符串,其中A
和B
都是有效「括号字符串」 - 可以被写作
(A)
的字符串,其中A
是一个有效的「括号字符串」
2,我采用了边遍历边删除的方法,首先删除一个字符的方法为s.erase(pos,1)
,然后边遍历边删除会面临2个问题: - 遍历退出条件为
s.size()
,不能再写n
,因为在动态变化 - 从前往后删除完
i
要--i
,然后++i
,保证i为下一个遍历元素,否则会跳过一个
然后还要考虑只剩左括号的也要删除,但因为栈是后入先出,相当于从后往前删,不会影响i
,不用--i
3.也可以用一个数组来记录要不要删除,然后再将s
迁移到答案中
代码
class Solution {
public:string minRemoveToMakeValid(string s) {int n = s.size();vector<int> stk;// 动态删除s,则遍历条件为s.size(),不能写nfor (int i = 0; i < s.size(); ++i) {if (s[i] == '(') {stk.push_back(i);} else if (s[i] == ')') {if (stk.empty()) {s.erase(i, 1);// 删除完要遍历下一个元素,先回退一个,然后会有++i--i;} else {stk.pop_back();}}}while (!stk.empty()) {int i = stk.back();s.erase(i, 1);stk.pop_back();}return s;}
};