前言: 感悟来自于leetcode做题时暴力解法的超时经历

信息标记

记录访问得到的信息： 我对你有所访问，必须留下点印记。否则下次我还需要对你重新访问来获取这个信息；

• 我将之命名为“蚂蚁行进”策略！！！

• 蚂蚁在找食物的时候会留下分泌物记录走过的路径；

• 类比我们访问元素之后留下信息标记一样；

比如 前缀和、 差分数组；以及记忆化计数器 、 （胜者树、败者树）

补充：使用差分数组的场景

比如一个装元素个数上亿的数组；我需要对一个范围内（上万个）的数据全部+1；

• 初始方案：范围遍历，全部+1；

• 上面方案遍历范围的时间复杂度为O(k)，k为范围内元素个数

• 如何简化？用一个差分数组记录当前元素i+1和上一个元素i之间的差值

• 那么只需要对这个范围的首元素的差分数组对应值+1；

• 范围后面一个元素的值+1

• 时间复杂度为O(2)

具体的例题

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

难度中等106收藏分享切换为英文接收动态反馈

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

来自 https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii/

//1.暴力解法（超时）
class Solution {
public:
   string removeDuplicates(string s, int k) {
    int length = -1;
    while (length != s.size()) {
        length = s.size();
        for (int i = 0, count = 1; i < s.size(); ++i) {
            if (i == 0 || s[i] != s[i - 1]) {
                count = 1;
            } else if (++count == k) {
                s.erase(i - k + 1, k);
                break;
            }
        }
    }
    return s;
}
};
//2.记忆化计数数组
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<int> count(s.size());
        for (int i = 0; i < s.size(); ++i) {
            if (i == 0 || s[i] != s[i-1]){
                count[i] = 1;
            } else {
                count[i] = count[i-1] + 1;
                if (count[i] == k) {
                    s.erase(i-k+1,k);
                    i = i - k; //后面迭代器失效，回退
                }
            }
        }
        return s;
    }
};