专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
在元宵节的时候雷军开启了直播，带大家参观了小米于北京海淀总部的食堂，食堂内某处悬挂着一块标语牌，上面写着“程序员是老大”。
雷军解释称：“这块牌匾以前金山的，算是一个口号，就是要讲程序员对金山的重要性。等我办小米以后，小米有类似的文化，叫工程师文化。因为无论是金山还是小米，都是工程师创办的一家公司，所以我们特别特别重视工程师，重视程序员。”
网友调侃道：“雷军是程序员，程序员是老大，老大是雷军，闭环了。”
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第20题：有效的括号。
问题描述
来源：LeetCode第20题
难度：简单
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例1：
输入：s = "(]" 输出：false
示例2：
输入：s = "()[]{}" 输出：true
1 <= s.length <= 10^4
s 仅由括号 '()[]{}' 组成
问题分析
这题是让判断字符串 s 是否是有效的括号，对于括号匹配问题，我们首先想到的是使用栈。
因为字符串 s 只包含 '()[]{}' ，如果遇到右括号，比如 ')'，']'，'}' ，就把与它们对应的左括号压入到栈中。
如果遇到左括号，比如 '('，'['，'{' ，栈顶元素就出栈，然后判断左括号和出栈的元素是否相等，如果不相等或者栈为空，说明不是有效的括号，直接返回 false 。
JAVA：
public boolean isValid(String s) { Stack
stk = new Stack<>(); // 创建一个栈 for ( char ch : s.toCharArray()) { // 如果是左括号，就把他们对应的右括号压栈 if (ch == '(') { stk.push( ')'); } else if (ch == '{') { stk.push( '}'); } else if (ch == '[') { stk.push( ']'); } else if (stk.isEmpty() || stk.pop() != ch) { return false; } } // 如果是有效的括号，左括号和右括号必须匹配，栈为空，否则就无效。 return stk.isEmpty(); }C++：
public: bool isValid(string s) { stack
stk; // 创建一个栈 for (char ch: s) { // 如果是左括号，就把他们对应的右括号压栈 if (ch == '(') { stk.push(')'); } else if (ch == '{') { stk.push('}'); } else if (ch == '[') { stk.push(']'); } else { if (stk.empty() || stk.top() != ch) return false; stk.pop(); } } // 如果是有效的括号，左括号和右括号必须匹配，栈为空，否则就无效。 return stk.empty(); }
Python：
def isValid(self, s: str) -> bool: stk = [] # 创建一个栈 for ch in s: # 如果是左括号，就把他们对应的右括号压栈 if ch == '(': stk.append(')') elif ch == '{': stk.append('}') elif ch == '[': stk.append(']') elif not stk or stk.pop() != ch: return False # 如果是有效的括号，左括号和右括号必须匹配，栈为空，否则就无效。 return not stk笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴