1、20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 2:
输入: "()[]{}"
输出: true
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}"
输出: true
class Solution { public: bool isValid(string s) { stack<char> parentheses; for(int i=0;i<s.size();++i) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]); else { if (parentheses.empty()) return false; if (s[i] == ')' && parentheses.top() != '(') return false; if (s[i] == ']' && parentheses.top() != '[') return false; if (s[i] == '}' && parentheses.top() != '{') return false; parentheses.pop(); } } return parentheses.empty(); } };
2、22. 括号生成
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
这道题给定一个数字n，让生成共有n个括号的所有正确的形式，对于这种列出所有结果的题首先还是考虑用递归Recursion来解，由于字符串只有左括号和右括号两种字符，而且最终结果必定是左括号3个，右括号3个，所以我们定义两个变量left和right分别表示剩余左右括号的个数，如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现')('这样的非法串，所以这种情况直接返回，不继续处理。如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新，若right大于0，则调用递归函数，同样要更新参数。
class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; generateDFS(n, n, "", res); return res; } void generateDFS(int left, int right, string out, vector<string> &res) { if(left>right) return ; if(left == 0 && right == 0) res.push_back(out); else { if (left > 0) generateDFS(left - 1, right, out + '(', res); if (right > 0) generateDFS(left, right - 1, out + ')', res); } } };
3、32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为"()()"
这里我们还是借助栈来求解，需要定义个start变量来记录合法括号串的起始位置，我们遍历字符串，如果遇到左括号，则将当前下标压入栈，如果遇到右括号，如果当前栈为空，则将下一个坐标位置记录到start，如果栈不为空，则将栈顶元素取出，此时若栈为空，则更新结果和i - start + 1中的较大值，否则更新结果和i - 栈顶元素中的较大值。
class Solution { public: int longestValidParentheses(string s) { int res = 0; int start = 0; stack<int> st; for(int i=0;i<s.size();++i) { if(s[i] == '(') st.push(i); else if(s[i] == ')') { if(st.empty()) start = i+1; else { st.pop(); if(st.empty()) res = max(res, i-start+1); else res = max(res,i-st.top()); } } } return res; } };
class Solution { public: int longestValidParentheses(string s) { int res = 0; int start = 0; stack<int> st; //记录左括号的位置 for(int i=0;i<s.size();++i) { if(s[i] == '(') //只有“（”入栈，右括号不入栈 st.push(i); else if(s[i] == ')') { if(st.empty()) //如果此时栈里左括号已经被消耗完了，没有额外的左括号用来配对当前的右括号了，那么当前的右括号就被单出来了，表明当前子串可以结束了，此时的右括号也成为了下一个group的分界点，此时右括号下标为index，所以下一个group的起始点为index+1,相当于skip掉当前的右括号。 start = i+1; else //如果此时栈不空，可能有两种情况，1）栈正好剩下1个左括号和当前右括号配对 2)栈剩下不止1个左括号 { st.pop(); if(st.empty()) //栈pop()之前正好剩下1个左括号，pop()之后，栈空了，此时group长度为pos-lastPos res = max(res, i-start+1); else res = max(res,i-st.top());//栈有pop()之前剩下不止1个左括号，此时额外多出的左括号使得新的group形成 } } } return res; } };