專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
3月24日在廣州阿里巴巴頂樓，有一位孕婦拉出“強(qiáng)烈抗議阿里惡意非法解雇臨產(chǎn)孕婦”的條幅。一時(shí)間在網(wǎng)上鬧的沸沸揚(yáng)揚(yáng)。
隨后阿里巴巴發(fā)表情況說明：由于近期淘寶買菜廣州區(qū)域業(yè)務(wù)調(diào)整，部分崗位變化，其中涉及服務(wù)公司“仁勵(lì)窩人力資源服務(wù)（廣州）有限公司”的一位生態(tài)員工（待產(chǎn)期）。該員工并未被辭退，并根據(jù)相關(guān)法律規(guī)定，照常發(fā)放在崗工資。
我查了以下仁勵(lì)窩人力資源服務(wù)（廣州）有限公司，經(jīng)營(yíng)范圍包括人力資源服務(wù)（勞務(wù)派遣服務(wù)），并且股權(quán)結(jié)構(gòu)中沒有阿里巴巴，所以不是阿里巴巴的子公司，應(yīng)該是一家外包公司。
至于維權(quán)，我覺得要看勞動(dòng)合同和誰簽，如果是和阿里簽的就去找阿里維權(quán)，如果是和外包公司簽的，就應(yīng)該去找外包去維權(quán)。
而對(duì)于辭退孕婦這件事網(wǎng)友的評(píng)論也是兩極分化，有的說公司沒權(quán)利辭退孕婦，還有的說一懷孕就入職，一生完孩子就離職，也很讓人頭疼。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1209題：刪除字符串中的所有相鄰重復(fù)項(xiàng) II，難度是中等。
給你一個(gè)字符串 s，「k 倍重復(fù)項(xiàng)刪除操作」將會(huì)從 s 中選擇 k 個(gè)相鄰且相等的字母，并刪除它們，使被刪去的字符串的左側(cè)和右側(cè)連在一起。你需要對(duì) s 重復(fù)進(jìn)行無限次這樣的刪除操作，直到無法繼續(xù)為止。
在執(zhí)行完所有刪除操作后，返回最終得到的字符串。本題答案保證唯一。
示例1：
輸入：s = "abcd", k = 2 輸出："abcd" 解釋：沒有要?jiǎng)h除的內(nèi)容。
示例2：
輸入：s = "deeedbbcccbdaa", k = 3 輸出："aa" 解釋： 先刪除 "eee" 和 "ccc"，得到 "ddbbbdaa" 再刪除 "bbb"，得到 "dddaa" 最后刪除 "ddd"，得到 "aa"
1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小寫英文字母。
問題分析
這題說的是如果有 k 個(gè)連續(xù)且相同的字符，就把它們給刪除。如果只是刪除相鄰且相同的字符我們可以直接使用一個(gè)棧就能解決，但這里還需要 k 個(gè)連續(xù)的，所以我們還需要在使用一個(gè)棧來記錄相鄰且相同元素的個(gè)數(shù)。
使用一個(gè)棧stk1來記錄所有的字符，相鄰且相同的字符只記錄一次，使用另外一個(gè)棧stk2來記錄該字符出現(xiàn)的次數(shù)，當(dāng)出現(xiàn)的次數(shù)等于 k 的時(shí)候，就把該字符以及它出現(xiàn)的次數(shù)從兩個(gè)棧中移除。
最后還需要把棧中沒有移除的字符轉(zhuǎn)化為字符串即可。
JAVA：
public String removeDuplicates(String s, int k) { Stack stk1 = new Stack<>();// 記錄當(dāng)前字符 Stack stk2 = new Stack<>();// 記錄當(dāng)前字符連續(xù)的個(gè)數(shù) for (char ch : s.toCharArray()) { if (!stk1.isEmpty() && ch == stk1.peek()) { // 如果當(dāng)前字符和棧頂字符一樣，就統(tǒng)計(jì)棧頂字符連續(xù)的個(gè)數(shù) stk2.push(stk2.pop() + 1); if (stk2.peek() == k) {// 連續(xù)出現(xiàn)k個(gè)，移除。 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();// 當(dāng)前字符出現(xiàn)的個(gè)數(shù) while (cnt-- > 0) ans.append(ch); } return ans.reverse().toString(); }C++：
public: string removeDuplicates(string s, int k) { stack
stk1;// 記錄當(dāng)前字符 stack
stk2;// 記錄當(dāng)前字符連續(xù)的個(gè)數(shù) for (char ch: s) { if (!stk1.empty() && ch == stk1.top()) { // 如果當(dāng)前字符和棧頂字符一樣，就統(tǒng)計(jì)棧頂字符連續(xù)的個(gè)數(shù) int cnt = stk2.top(); stk2.pop(); stk2.push(cnt + 1); if (stk2.top() == k) {// 連續(xù)出現(xiàn)k個(gè)，移除。 stk1.pop(); stk2.pop(); } } else { stk1.push(ch); stk2.push(1); } } string ans; while (!stk2.empty()) { char ch = stk1.top(); int cnt = stk2.top();// 當(dāng)前字符出現(xiàn)的個(gè)數(shù) stk1.pop(); stk2.pop(); while (cnt-- > 0) ans += ch; } reverse(ans.begin(), ans.end()); return ans; }
筆者簡(jiǎn)介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。
熱門跟貼