每天算法刷题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 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 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 stk; // 动态删除s,则遍历条件为s.size(),不能写n for (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; }};