C++ 中移除字串中所有相鄰重複字元 II

假設給定一個字串 s，k 次重複移除包括從字串 s 中選擇 k 個相鄰且相等的字母並將其移除，導致已刪除子字串的左側和右側連線在一起。我們將對給定的字串 s 重複進行 k 次重複移除，直到我們無法進行任何更改。我們必須找到所有此類重複移除後最終的字串。因此，如果輸入類似於 s = “deeedbbcccbdaa”，k = 3，則輸出將是 “aa”，首先刪除 “eee” 和 “ccc”，我們將得到 “ddbbbaa”，然後刪除 “bbb”，字串將是 “dddaa”，然後刪除 “ddd”，輸出將是 “aa”

為了解決這個問題，我們將遵循以下步驟：

  • ans := 空字串
  • 建立一個字元-整數對的棧，n := 字串的大小
  • 對於 i 從 0 到 n
    • x := s[i]
    • 如果棧不為空且棧頂元素的整數部分 = k，則從棧中刪除頂元素
    • 如果 i = n，則中斷
    • 如果棧為空或棧頂的字元不是 x，則將對 (x, 1) 插入到棧中，並將 i 增加 1
    • 否則增加棧頂元素的整數部分，並將 i 增加 1
  • 當棧不為空時
    • temp := 棧頂元素
    • 當 temp 的整數部分不為 0 時
      • ans := ans + temp 的字元部分
      • 將 temp 的整數部分減少 1
    • 從棧中刪除頂元素
  • 反轉 ans 字串並返回。

讓我們看看下面的實現以更好地理解：

示例

線上演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string removeDuplicates(string s, int k) {
      string ans = "";
      stack < pair<char, int> > st;
      int n = s.size();
      for(int i = 0; i <= n;){
         char x = s[i];
         if(!st.empty() && st.top().second == k)st.pop();
         if(i == n)break;
         if(st.empty() || st.top().first != x){
            st.push({x, 1});
            i++;
         } else {
            st.top().second++;
            i++;
         }
      }
      while(!st.empty()){
         pair <char, int> temp = st.top();
         while(temp.second--) ans += temp.first;
         st.pop();
      }
      reverse(ans.begin(), ans.end());
      return ans;
   }
};
main(){
   Solution ob;
   cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
}

輸入

"deeedbbcccbdaa"
3

輸出

aa

更新於：2020年4月30日

620 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告