20. 有效的括号
难度简单1894收藏分享切换为英文接收动态反馈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true示例 2:
输入: "()[]{}" 输出: true示例 3:
输入: "(]" 输出: false示例 4:
输入: "([)]" 输出: false示例 5:
输入: "{[]}" 输出: true class Solution { public: bool isValid(string str) { stack<char> s; // 如果括号数量是奇数，直接说明就是错误的 if(str.size() % 2 == 1) return false; for(char c: str) { // 遇到左括号就入栈 if(c=='(' ){ s.push(')'); continue; } if(c=='[') { s.push(']'); continue; } if(c=='{') { s.push('}'); continue; } // 如果没有左括号入栈直接说明遇到的第一个就是右括号，不匹配，返回false // 不能用下面的很长的if来判断，因为没有栈顶元素，使用top方法会报错所以单独写这个针对第一个元素就是右括号的情况 if(s.empty()) return false; // 遇到右括号就和栈顶元素匹配，正确匹配就出栈，不正确匹配就返回false if(c==s.top()){ s.pop(); continue; } else{ return false; } } // 直到所有括号都比较完并且栈为空就返回true，否则返回false return s.empty() ? true : false; } };python
class Solution: def isValid(self, s: str) -> bool: dic = {'(':')',"{":"}","[":"]"} res = [] for c in s: if c in dic.keys(): res.append(dic[c]) elif len(res)==0 or c!=res.pop(): return False if not res: return True else: return False921. 使括号有效的最少添加
难度中等66收藏分享切换为英文接收动态反馈
给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者它可以被写作 (A)，其中 A 是有效字符串。给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())" 输出：1示例 2：
输入："(((" 输出：3示例 3：
输入："()" 输出：0示例 4：
输入："()))((" 输出：4
提示：
S.length <= 1000S 只包含 '(' 和 ')' 字符。因为res记录的左括号的插入次数，need记录了右括号的需求，
class Solution { public: int minAddToMakeValid(string s) { //res 记录插入数量 int res = 0; //need 记录右括号需求 int need = 0; for(int i=0;i<s.size();i++) { if(s[i]=='(') need++; //需要一个右括号 if(s[i]==')') { need--; if(need == -1) { need=0; res++; } } } return res+need; } };
1541. 平衡括号字符串的最少插入次数
难度中等12收藏分享切换为英文接收动态反馈
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
任何左括号 '(' 必须对应两个连续的右括号 '))' 。左括号 '(' 必须在对应的连续两个右括号 '))' 之前。比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))" 输出：1 解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。示例 2：
输入：s = "())" 输出：0 解释：字符串已经平衡了。示例 3：
输入：s = "))())(" 输出：3 解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。示例 4：
输入：s = "((((((" 输出：12 解释：添加 12 个 ')' 得到平衡字符串。示例 5：
输入：s = ")))))))" 输出：5 解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
提示：
1 <= s.length <= 10^5s 只包含 '(' 和 ')' 。class Solution { public: int minInsertions(string s) { int res = 0,need = 0; for (int i = 0; i<s.size();i++) { if(s[i]=='(') { need+=2; if(need %2==1) { res++; //插入一个右字符串 need--; } } if(s[i]==')') { need--; if(need == -1) { res++; need = 1; } } } return res+need; } };
参考链接：http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487246&idx=1&sn=4a514020ce9dc8777e2d1d503188b62b&chksm=9bd7f106aca078108102fe76799983ee8ea3bd759508e6dbfe87bc9da6edbeb8b8dd73deb0d7#rd
