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

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

3月24日在廣州阿里巴巴頂樓，有一位孕婦拉出“強烈抗議阿里惡意非法解雇臨產孕婦”的條幅。一時間在網上鬧的沸沸揚揚。

隨后阿里巴巴發表情況說明：由于近期淘寶買菜廣州區域業務調整，部分崗位變化，其中涉及服務公司“仁勵窩人力資源服務（廣州）有限公司”的一位生態員工（待產期）。該員工并未被辭退，并根據相關法律規定，照常發放在崗工資。

我查了以下仁勵窩人力資源服務（廣州）有限公司，經營范圍包括人力資源服務（勞務派遣服務），并且股權結構中沒有阿里巴巴，所以不是阿里巴巴的子公司，應該是一家外包公司。

至于維權，我覺得要看勞動合同和誰簽，如果是和阿里簽的就去找阿里維權，如果是和外包公司簽的，就應該去找外包去維權。

而對于辭退孕婦這件事網友的評論也是兩極分化，有的說公司沒權利辭退孕婦，還有的說一懷孕就入職，一生完孩子就離職，也很讓人頭疼。

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

來看下今天的算法題，這題是LeetCode的第1209題：刪除字符串中的所有相鄰重復項 II，難度是中等。

給你一個字符串 s，「k 倍重復項刪除操作」將會從 s 中選擇 k 個相鄰且相等的字母，并刪除它們，使被刪去的字符串的左側和右側連在一起。你需要對 s 重復進行無限次這樣的刪除操作，直到無法繼續為止。

在執行完所有刪除操作后，返回最終得到的字符串。本題答案保證唯一。

示例1：

輸入：s = "abcd", k = 2 輸出："abcd" 解釋：沒有要刪除的內容。

示例2：

輸入：s = "deeedbbcccbdaa", k = 3 輸出："aa" 解釋： 先刪除 "eee" 和 "ccc"，得到 "ddbbbdaa" 再刪除 "bbb"，得到 "dddaa" 最后刪除 "ddd"，得到 "aa"

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

• 2 <= k <= 10^4

• s 中只含有小寫英文字母。

問題分析

這題說的是如果有 k 個連續且相同的字符，就把它們給刪除。如果只是刪除相鄰且相同的字符我們可以直接使用一個棧就能解決，但這里還需要 k 個連續的，所以我們還需要在使用一個棧來記錄相鄰且相同元素的個數。

使用一個棧stk1來記錄所有的字符，相鄰且相同的字符只記錄一次，使用另外一個棧stk2來記錄該字符出現的次數，當出現的次數等于 k 的時候，就把該字符以及它出現的次數從兩個棧中移除。

最后還需要把棧中沒有移除的字符轉化為字符串即可。

JAVA：

public String removeDuplicates(String s, int k) {     Stack stk1 =  new Stack<>();// 記錄當前字符     Stack stk2 =  new Stack<>();// 記錄當前字符連續的個數     for (char ch : s.toCharArray()) {         if (!stk1.isEmpty() && ch == stk1.peek()) {             // 如果當前字符和棧頂字符一樣，就統計棧頂字符連續的個數             stk2.push(stk2.pop() + 1);             if (stk2.peek() == k) {// 連續出現k個，移除。                 stk1.pop();                 stk2.pop();             }         } else {             stk1.push(ch);             stk2.push(1);         }     }     StringBuilder ans = new StringBuilder();     while (!stk2.isEmpty()) {         char ch = stk1.pop();         int cnt = stk2.pop();// 當前字符出現的個數         while (cnt-- > 0)             ans.append(ch);     }     return ans.reverse().toString(); }

C++：

public:     string removeDuplicates(string s, int k) {         stack

 stk1;// 記錄當前字符         stack

 stk2;// 記錄當前字符連續的個數         for (char ch: s) {             if (!stk1.empty() && ch == stk1.top()) {                 // 如果當前字符和棧頂字符一樣，就統計棧頂字符連續的個數                 int cnt = stk2.top();                 stk2.pop();                 stk2.push(cnt + 1);                 if (stk2.top() == k) {// 連續出現k個，移除。                     stk1.pop();                     stk2.pop();                 }             } else {                 stk1.push(ch);                 stk2.push(1);             }         }         string ans;         while (!stk2.empty()) {             char ch = stk1.top();             int cnt = stk2.top();// 當前字符出現的個數             stk1.pop();             stk2.pop();             while (cnt-- > 0)                 ans += ch;         }         reverse(ans.begin(), ans.end());         return ans;     }

筆者簡介

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