專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

現在是3月份，正是找工作的時候，大家不要被一些所謂的高薪工作給迷惑了，尤其是國外的工作，如果是國企外派過去的倒還好一些，如果是自己在網上找的，一定要謹慎。

最近網上有三人收到一條短信，大致內容是給他們提供一份工作，工作內容是剪輯和拍攝，一個月賺七八萬，五六十萬的都有。雖然他們并無相關工作經驗，仍按照對方指示來到廣西，企圖偷渡出境。幸好，出租車司機發現并報了警，民警及時把他們攔截。

我記得在2019年和2020年找工作的時候，也收到一些需要出國的工作，工資要比國內高一些，一個是菲律賓一個是泰國，他們說這些國家軟件開發不行，需要國內的人過去，我當時沒考慮到是詐騙，但覺得太遠，直接拒絕了。還好沒去，印象中那幾年招人到東南亞的挺多的。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1249題：移除無效的括號，難度中等 。

給你一個由 '('、')' 和小寫字母組成的字符串 s。你需要從字符串中刪除最少數目的 '(' 或者 ')' （可以刪除任意位置的括號)，使得剩下的「括號字符串」有效。請返回任意一個合法字符串。

示例1：

輸入：s = "lee(t(c)o)de)" 輸出："lee(t(c)o)de" 解釋："lee(t(co)de)" , "lee(t(c)ode)" 也是一個可行答案。

示例2：

輸入：s = "a)b(c)d" 輸出："ab(c)d"

• 1 <= s.length <= 10^5

• s[i] 可能是 '('、')' 或英文小寫字母

問題分析

這題說的是刪除最少的括號，使剩下的括號有效，其中字母不要刪除。實際上這是一道括號匹配問題，匹配的時候我們只需要考慮左括號和右括號，其它的字符不需要考慮。

我們使用一個棧只記錄左括號 '(' 的下標，如果遇到左括號就把它壓棧，然后標記為刪除狀態，這里為什么要把它標記為可刪除狀態？因為后面如果能遇到匹配的右括號 ')' ，再把它恢復為不可刪除狀態，如果后面遇不到匹配的右括號 ')' ，說明這個左括號是無效。

如果遇到右括號 ')' ，并且棧是空的，說明沒有和這個右括號匹配的左括號，把這個右括號標記為可刪除狀態。如果棧不為空，那么當前右括號就和棧頂的左括號是匹配的，棧頂的左括號出棧，把它們都標記為不可刪除狀態。

最后在遍歷整個字符串，去掉刪除狀態的括號即可。

JAVA：

public String minRemoveToMakeValid(String s) {     boolean[] deleted = newboolean[s.length()];// 標記哪些括號是被刪除的     Stack stk =  new Stack<>();     for (int i = 0; i < s.length(); i++) {         if (s.charAt(i) == '(') {             // 左括號，先標記為刪除狀態，如果能遇到右括號，再標記為不可刪除狀態。             stk.push(i);             deleted[i] = true;         } elseif (s.charAt(i) == ')') {             if (stk.empty()) {                 // 棧是空的，說明當前右括號沒有可匹配的，標記為刪除狀態。                 deleted[i] = true;             } else {                 // 這里的右括號和棧頂的左括號匹配，標記為不可刪除狀態。                 deleted[stk.pop()] = false;                 deleted[i] = false;             }         }     }     // 去掉刪除狀態的字符。     StringBuilder ans = new StringBuilder();     for (int i = 0; i < s.length(); i++) {         if (!deleted[i])             ans.append(s.charAt(i));     }     return ans.toString(); }

C++：

public:     string minRemoveToMakeValid(string s) {         vector

  deleted(s.length(), false);// 標記哪些括號是被刪除的         stack

 stk;         for (int i = 0; i < s.length(); i++) {             if (s[i] == '(') {                 // 左括號，先標記為刪除狀態，如果能遇到右括號，再標記為不可刪除狀態。                 stk.push(i);                 deleted[i] = true;             } elseif (s[i] == ')') {                 if (stk.empty()) {                     // 棧是空的，說明當前右括號沒有可匹配的，標記為刪除狀態。                     deleted[i] = true;                 } else {                     // 這里的右括號和棧頂的左括號匹配，標記為不可刪除狀態。                     deleted[stk.top()] = false;                     stk.pop();                     deleted[i] = false;                 }             }         }         // 去掉刪除狀態的字符。         string ans;         for (int i = 0; i < s.length(); i++) {             if (!deleted[i])                 ans += s[i];         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。