小米食堂挂牌匾“程序员是老大”，遭网友调侃。

专栏：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算法文档 。