前言: 感悟來(lái)自于leetcode做題時(shí)暴力解法的超時(shí)經(jīng)歷

信息標(biāo)記

記錄訪問(wèn)得到的信息： 我對(duì)你有所訪問(wèn)，必須留下點(diǎn)印記。否則下次我還需要對(duì)你重新訪問(wèn)來(lái)獲取這個(gè)信息；

• 我將之命名為“螞蟻行進(jìn)”策略！??！

• 螞蟻在找食物的時(shí)候會(huì)留下分泌物記錄走過(guò)的路徑；

• 類比我們?cè)L問(wèn)元素之后留下信息標(biāo)記一樣；

比如 前綴和、 差分?jǐn)?shù)組；以及記憶化計(jì)數(shù)器 、 （勝者樹(shù)、敗者樹(shù)）

補(bǔ)充：使用差分?jǐn)?shù)組的場(chǎng)景

比如一個(gè)裝元素個(gè)數(shù)上億的數(shù)組；我需要對(duì)一個(gè)范圍內(nèi)（上萬(wàn)個(gè)）的數(shù)據(jù)全部+1；

• 初始方案：范圍遍歷，全部+1；

• 上面方案遍歷范圍的時(shí)間復(fù)雜度為O(k)，k為范圍內(nèi)元素個(gè)數(shù)

• 如何簡(jiǎn)化？用一個(gè)差分?jǐn)?shù)組記錄當(dāng)前元素i+1和上一個(gè)元素i之間的差值

• 那么只需要對(duì)這個(gè)范圍的首元素的差分?jǐn)?shù)組對(duì)應(yīng)值+1；

• 范圍后面一個(gè)元素的值+1

• 時(shí)間復(fù)雜度為O(2)

具體的例題

1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II

難度中等106收藏分享切換為英文接收動(dòng)態(tài)反饋

給你一個(gè)字符串 s，「k 倍重復(fù)項(xiàng)刪除操作」將會(huì)從 s 中選擇 k 個(gè)相鄰且相等的字母，并刪除它們，使被刪去的字符串的左側(cè)和右側(cè)連在一起。

你需要對(duì) s 重復(fù)進(jìn)行無(wú)限次這樣的刪除操作，直到無(wú)法繼續(xù)為止。

在執(zhí)行完所有刪除操作后，返回最終得到的字符串。

來(lái)自 https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii/

//1.暴力解法（超時(shí)）
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.記憶化計(jì)數(shù)數(shù)組
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;
    }
};