算法与数据结构——括号问题一网打尽

本篇leetcode题解

leetcode 20 有效的括号

leetcode 921 使括号有效的最少添加

leetcode 1541 平衡括号字符串的最少插入次数

======================================================================================

leetcode 20 有效的括号

为什么在解决括号匹配问题的时候,需要用到栈这个数据结构呢？

我们回想栈的典型特点，先进后出，对于括号匹配问题来说。从中间往两边，距离最近且相互匹配的一对便是一组括号。

因此对于括号问题来说，我们可以把其分为左右两个部分来处理，对于左括号而言，其作用是提供一个匹配需求（入栈），表明需要为其搭配一个右括号。而对于右括号而已，目的是使用它成功匹配到对应的左括号，完成一组匹配，减少栈内的元素。

因此这道括号的匹配题就是这个思想，无法是匹配的元素变成了三种，只需要用or将它们连接即可！

class Solution { public: bool isValid(string s) { stack<char> st; //if(s.size()==0) return false; for(int i = 0;i<s.size();i++){ if(s[i] == '(' || s[i]=='{' || s[i]=='['){ st.push(s[i]); } else { if(!st.empty() && st.top()==getChar(s[i])) st.pop(); else return false; } } return st.empty(); } char getChar(char c){ if(c == ']') return '['; else if(c == '}') return '{'; else return '('; } };

注意： 对栈进行判断栈顶元素时，st.top（的前提也得是，!st.empty()，栈非空. 逻辑问题。

======================================================================================

leetcode 921 使括号有效的最少添加

这道题问使得有效的最少添加数量。无非两种情况:

左括号不足，需要添加左括号。

右括号不足，需要添加右括号。

最终返回总共需要的括号数（左+右）。

所以当然使用两个计数器对左右括号的需求进行记录，分别为res和need。

这就没必要用栈了，我们只需要保添加后，左右符号的数量匹配即可。

代码如下：

class Solution { public: int minAddToMakeValid(string S) { int res = 0; int need = 0; for(int i = 0;i<S.size();i++){ if(S[i] == '(') need++; //有右括号需求 else{ need--; if(need == -1){ //有左括号填补需求 res++; need = 0; } } } return res+need; //左括号+右括号需求 } };

======================================================================================

leetcode 1541 平衡括号字符串的最少插入次数

class Solution { public: int minInsertions(string s) { int res = 0; // 插入括号需要 int need = 0; //右括号需要 int size = s.size(); for(int i=0;i<s.size();i++){ if(s[i]=='('){ need+=2; //添加右括号需求 if(need%2==1){ //如果右括号为奇数，则需要插入一个右括号 res++; //插入一个右括号 need--; //对右括号的需求减1 } }else{ need--; if(need==-1){ //说明右括号多了 res++; //需要插入一个左括号 need=1; //由于一个左括号-对应两个右括号，所以对右括号的需求变为1 } } } return res+need; } };

在本题中，由于一个左括号匹配两个右括号，那么括号的插入情况会对应出现，左括号插入和右括号插入。因此本题的一个难点在于考虑到：

当前符号为左括号时，但是对应的右括号是奇数，应该如何处理。

写在最后

括号问题本质上是想清楚匹配的情况，不管是符号本身的匹配，还是左右数量的匹配也好。都要保证对应加入\减去的操作是对应起来的。