前言: 感悟来自于leetcode做题时暴力解法的超时经历
信息标记
记录访问得到的信息： 我对你有所访问，必须留下点印记。否则下次我还需要对你重新访问来获取这个信息；
我将之命名为“蚂蚁行进”策略！！！
蚂蚁在找食物的时候会留下分泌物记录走过的路径；
类比我们访问元素之后留下信息标记一样；
比如 前缀和、 差分数组；以及记忆化计数器 、 （胜者树、败者树）
补充：使用差分数组的场景
比如一个装元素个数上亿的数组；我需要对一个范围内（上万个）的数据全部+1；
初始方案：范围遍历，全部+1；
上面方案遍历范围的时间复杂度为O(k)，k为范围内元素个数
如何简化？用一个差分数组记录当前元素i+1和上一个元素i之间的差值
那么只需要对这个范围的首元素的差分数组对应值+1；
范围后面一个元素的值+1
时间复杂度为O(2)
具体的例题
难度中等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;
}
};
