專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
現(xiàn)在是3月份，正是找工作的時候，大家不要被一些所謂的高薪工作給迷惑了，尤其是國外的工作，如果是國企外派過去的倒還好一些，如果是自己在網(wǎng)上找的，一定要謹(jǐn)慎。
最近網(wǎng)上有三人收到一條短信，大致內(nèi)容是給他們提供一份工作，工作內(nèi)容是剪輯和拍攝，一個月賺七八萬，五六十萬的都有。雖然他們并無相關(guān)工作經(jīng)驗(yàn)，仍按照對方指示來到廣西，企圖偷渡出境。幸好，出租車司機(jī)發(fā)現(xiàn)并報了警，民警及時把他們攔截。
我記得在2019年和2020年找工作的時候，也收到一些需要出國的工作，工資要比國內(nèi)高一些，一個是菲律賓一個是泰國，他們說這些國家軟件開發(fā)不行，需要國內(nèi)的人過去，我當(dāng)時沒考慮到是詐騙，但覺得太遠(yuǎn)，直接拒絕了。還好沒去，印象中那幾年招人到東南亞的挺多的。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是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] 可能是 '('、')' 或英文小寫字母
問題分析
這題說的是刪除最少的括號，使剩下的括號有效，其中字母不要刪除。實(shí)際上這是一道括號匹配問題，匹配的時候我們只需要考慮左括號和右括號，其它的字符不需要考慮。
我們使用一個棧只記錄 如果遇到右括號 ')' ，并且棧是空的，說明沒有和這個右括號匹配的左括號，把這個右括號標(biāo)記為可刪除狀態(tài)。如果棧不為空，那么當(dāng)前右括號就和棧頂?shù)淖罄ㄌ柺瞧ヅ涞模?a class="keyword-search" >棧頂
最后在遍歷整個字符串，去掉刪除狀態(tài)的括號即可。
JAVA：
public String minRemoveToMakeValid(String s) { boolean[] deleted = newboolean[s.length()];// 標(biāo)記哪些括號是被刪除的 Stack stk = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { // 左括號，先標(biāo)記為刪除狀態(tài)，如果能遇到右括號，再標(biāo)記為不可刪除狀態(tài)。 stk.push(i); deleted[i] = true; } elseif (s.charAt(i) == ')') { if (stk.empty()) { // 棧是空的，說明當(dāng)前右括號沒有可匹配的，標(biāo)記為刪除狀態(tài)。 deleted[i] = true; } else { // 這里的右括號和棧頂?shù)淖罄ㄌ柶ヅ?，?biāo)記為不可刪除狀態(tài)。 deleted[stk.pop()] = false; deleted[i] = false; } } } // 去掉刪除狀態(tài)的字符。 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);// 標(biāo)記哪些括號是被刪除的 stack
stk; for (int i = 0; i < s.length(); i++) { if (s[i] == '(') { // 左括號，先標(biāo)記為刪除狀態(tài)，如果能遇到右括號，再標(biāo)記為不可刪除狀態(tài)。 stk.push(i); deleted[i] = true; } elseif (s[i] == ')') { if (stk.empty()) { // 棧是空的，說明當(dāng)前右括號沒有可匹配的，標(biāo)記為刪除狀態(tài)。 deleted[i] = true; } else { // 這里的右括號和棧頂?shù)淖罄ㄌ柶ヅ?，?biāo)記為不可刪除狀態(tài)。 deleted[stk.top()] = false; stk.pop(); deleted[i] = false; } } } // 去掉刪除狀態(tài)的字符。 string ans; for (int i = 0; i < s.length(); i++) { if (!deleted[i]) ans += s[i]; } return ans; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼