專欄：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算法文檔 。