Leetcode 20：有效的括号
题目描述
给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
代码实现
bool isValid(string s) { if (s.empty()) return true; if (s.size() % 2 == 1) return false; stack<char> tt; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') tt.push(')'); else if (s[i] == '[') tt.push(']'); else if (s[i] == '{') tt.push('}'); else if (tt.empty() || tt.top() != s[i]) return false; else tt.pop(); } return tt.empty();}复杂度
时间复杂度：O(n)，n为字符串长度
空间复杂度：O(n)，n为字符串长度
Leetcode 22：括号生成
题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()"]解题思路
用回溯法可以比较容易的做出来，因为前面回溯法说的比较多了，这里就不再累述。但是有一点注意的是，backtrack()中第三个判断一定要是right<left才可以，而不是right<n，因为right的数量目标是等于left，在已经有了left个左括号的时候，右括号数量right不能超过left。
代码实现
void backtrack(int left,int right, int n, string& s, vector<string>& result){ if (left == n && right == n) { result.push_back(s); return; } if (left < n) { s += "("; backtrack(left + 1, right, n, s, result); s.pop_back(); } //下面的意思是，右括号不可能多于左括号的数量，当然也不能少于左括号的数量 if (right < left) { s += ")"; backtrack(left, right + 1, n, s, result); s.pop_back(); } }vector<string> generateParenthesis(int n) { vector<string> res; string s; backtrack(0, 0, n, s, res); return res;}复杂度
Leetcode 32：最长有效括号
题目说明
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
解题思路
参考：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/c-liang-ci-bian-li-jie-fa-by-da-li-wang/
代码实现
int longestValidParentheses(string s) { int res = 0; int left = 0; int mark = 0; //从左到右 for (int i = 0; i < s.size(); ++i) { int prev_mark = mark; mark = max(0, mark + ((s[i] == '(') ? 1 : -1)); if (mark == 0) { if (prev_mark > 0) { res = max(i - left + 1, res); } else { left = i + 1; } } } mark = 0; int right = s.size() - 1; //从右到左 for (int i = s.size() - 1; i >= 0; --i) { int prev_mark = mark; mark = max(0, mark + ((s[i] == ')') ? 1 : -1)); if (mark == 0) { if (prev_mark > 0) { res = max(right - i + 1, res); } else { right = i - 1; } } } return res;}复杂度
空间复杂度：O(n)【dp数组长度】
时间复杂度：O(n)
