1209删除字符串中所有相邻重复项II

下面是题目

下面是代码模板

class Solution {
public:
    string removeDuplicates(string s, int k) {
    }
};

下面是一种好方法

class Solution {
public:
    string removeDuplicates(string s, int k) {
//并不能用map<pair<char,int>>来存储，否 则 s= yhhswyyyy，k=4 
//这种数据，就会出来yhhsy,而不是yhhsw..你懂吧
//用vector，允许重复出现，就不会在原来int的基础上叠加
      vector<pair<char,int>> st;
        for(auto& i : s){
            if(!st.empty() && st.back().first == i){
//如果这一个数据到达k了，直接删除就完事了，如果用stack存储还要再做一个循环pop()       
                if(++st.back().second == k){
                    st.pop_back();
                }
            }
            else{
                st.push_back(make_pair(i,1));
            }
        }
        string res;
        //最后时复盘阶段，就是按照pair<char,int>输出int个char
        for(auto& i : st){
            int l = i.second;
            while(l--)
                res += i.first;
        }
        return res;
    }
};

递归大法好

class Solution {
public:
    string removeDuplicates(string s, int k) {
        for(int i=1,len=1;i<s.size();i++){
            if(s[i]==s[i-1]){
                len++;
            }else{
                len=1;
            }
            if(len==k){
      //龙珠大法好！，如果中间那部分要删除，那么为什么不把头尾两段连起来再搞一次呢
              return removeDuplicates(s.substr(0,i-k+1)+s.substr(i+1),k);
            }
        }
        return s;
    }
};

用stack也是很香的啊，为啥我想不到呢？

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<int> cnt;
  //和用vector存储不同，stack仅仅存储数字，而在s上之间用erase修改
        for(int i = 0; i < s.size(); ++i){
            if (i == 0 || s[i] != s[i-1]){
                cnt.push(1);
            }
            else {
                cnt.top() += 1;
            }
 //如果发现栈顶=k，就说明要删除了，删除部分就是s从i-k+1开始，删除k个字符
            if (cnt.top() == k){
                cnt.pop();
                s.erase(i-k+1,k);
//别忘了把i-k，因为现在的s[i]已经不是刚才的s[i]了
                i = i - k;
            }
        }
        return s;
    }
};

我提交的几个方法和错误点

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<char>stk;
        map <char,int> mp;
        int temp =1;
        string res;
        for(char c:s)
        {
            if(mp.find(c)==mp.end()){
                mp.insert(make_pair(c,1));
            } else{
                mp[c]++;
            }
            stk.push(c);
            if(mp[c]==k) {
                for (int i = k; i; i--) {
                    stk.pop();
                }
            }
        }
        while(!stk.empty())
        {
            res.insert(0,1,stk.top());
            stk.pop();
        }
        return res;
    }
};
/*
输入：
"pbbcggttciiippooaais"
2
输出：
"ppis"
预期：
"ps"
*/
//iiippooaai这里，中间的删掉以后，无法判断i之前出现过几次

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<char>stk;
        map <char,int> mp;
        int temp =1;
        string res;
        for(char c:s)
        {
            if(mp.find(c)==mp.end()){
                mp.insert(make_pair(c,temp));
            } else{
                mp[c]++;
            }
            stk.push(c);
            if(mp[c]==k) {
                for (int i = k; i; i--) {
                    stk.pop();
                }
                mp[c]-=k;
            }
        }

        while(!stk.empty())
        {
            res.insert(0,1,stk.top());
            stk.pop();
        }
        return res;
    }
};
/*
输入：
"yfttttfbbbbnnnnffbgffffgbbbbgssssgthyyyy"
4
输出：
"ybty"
预期：
"ybth"
*/
//并不能用map<pair<char,int>>来存储，否 则 s= yhhswyyyy，k=4