###### tags: `CP` `BOOK`

# [CP]Leetcode & 奇怪的tricks
> 本篇記錄寫力扣題目遇到的一些tricks以及一些常見的作法。
::: danger
這篇可能有部分內容會偏離CP本身，因為裡面會提及一些比較適合面試的實作，以及面試可能會被要求的樣式，但在CP中根本不會有這種要求。
:::

### 1. 較不直觀的狀態轉移
[446. Arithmetic Slices II - Subsequence](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/description/)
#### 題解
定義的狀態沒有辦法很直觀求到答案，而是在求解過程中算答案。
$f[i][d]$為下標i元素為數列最末元素，且公差為d時，得到的等差數列數量；**其中，在這個狀態中，長度為2也要被算進去!!**。因此有
$$f[i][d] = f[j][d]+1, j<i$$
假設有數列[2,4,6]，則$f[1][2] = 1$，但數組[2,4]不為題目下合格的AP；而$f[2][2] = 2$，其中包含$[2,4,6]$和$[2,4]$。
當我們在統計答案的時候，長度為2的解不能被算進去。
有以下兩種方法：
#### AC Code [法一]

#define vt vector
#define ll long long
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //f[i][d] = f[i-j][d]+1, d = nums[i]-nums[j]
        ll n = nums.size(), ans = 0;
        vt<map<ll,ll>> f(n);
        for(ll i = 1; i<n; ++i){
            for(ll j = 0; j<i; ++j){
                ll d = (ll)nums[i]-(ll)nums[j];
                if(f[j].count(d)){
                    f[i][d]+=f[j][d];
                    ans+=f[j][d];
                }
                f[i][d]+=1;
            }
        }
        return ans;
    }
};

#### AC Code [法二]

#define vt vector
#define ll long long
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //f[i][d] = f[i-j][d]+1, d = nums[i]-nums[j]
        ll n = nums.size(), ans = 0;
        vt<map<ll,ll>> f(n);
        for(ll i = 1; i<n; ++i){
            for(ll j = 0; j<i; ++j){
                ll d = (ll)nums[i]-(ll)nums[j];
                if(f[j].count(d)){
                    f[i][d]+=f[j][d];
                    //ans+=f[j][d];
                }
                f[i][d]+=1;
            }
        }
        for(ll i = 1; i<n; ++i){
            for(auto& d:f[i]){ans+=d.second;}
            ans-=i;
        }
        return ans;
    }
};

- 法一不直觀
- 法二最後在計算答案的時候，要扣除所有長度為2的子序列，也就是$i-1$，因為第i個元素可以和前面所有$i-1$的元素形成等差子序列(雖然說2個不叫等差)

這一點的難點在為了讓轉移式成立，定義的狀態與題意的不一樣(也和等差的定義不同；3個才能叫等差)。

### 2. Exactly k times
Exactly k = (At most k) - (At most k-1)

#### 例題：[992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/description/?envType=daily-question&envId=2024-03-30)

### 3. BFS & 層序 BFS & Dijkstra
題目：給一張圖，邊的權重為1，求兩點之間的最短路徑。
分析：套用最短路徑演算法即可；但權值為1時，可以用BFS求解。
#### 例題：[752. Open the Lock](https://leetcode.com/problems/open-the-lock/description/?envType=daily-question&envId=2024-04-22)
#### AC Code [BFS]

#define P pair<string,int>
class Solution {
public:
    static const int mxN = 1e9+7;
    map<string, int> vis;
    map<string, int> de;
    pair<string,string> neighbor(string a, int x){
        string r1, r2;
        r1 = r2 = a;
        char c = a[x];
        if(c=='0'){
            r1[x] = '1';
            r2[x] = '9';
        }
        else if(c=='9'){
            r1[x] = '8';
            r2[x] = '0';
        }
        else{
            r1[x] = c+1;
            r2[x] = c-1;
        }
        return {r1, r2};
    }
    int openLock(vector<string>& deadends, string target) {
        for(auto& d:deadends){
            de[d] = 1;
        }
        queue<P> q;
        if(de["0000"]){return -1;}
        q.push({"0000", 0});
        while(q.size()){
            auto x = q.front(); q.pop();
            if(x.first==target){return x.second;}
            for(int i = 0; i<4; ++i){
                auto [p1, p2] = neighbor(x.first, i);
                if(!vis[p1] && !de[p1]){
                    vis[p1] = 1;
                    q.push({p1, x.second+1});
                }
                if(!vis[p2]&& !de[p2]){
                    vis[p2] = 1;
                    q.push({p2, x.second+1});
                }
            }
            
        }
        
        return -1;
    }
};

#### AC Code [層序BFS]
在上面的程式中，放進queue裡面的元素有個，第二個元素`int`是為了記錄當前的最短路徑。實際上，BFS有貪婪的特性，在**權值為1下**，先遍歷到的節點可以視為最短路徑；因此，可以透過層序式的BFS來直接對最短路徑**計數**。

#define P pair<string,int>
class Solution {
public:
    static const int mxN = 1e9+7;
    map<string, int> vis;
    map<string, int> de;
    pair<string,string> neighbor(string a, int x){
        string r1, r2;
        r1 = r2 = a;
        char c = a[x];
        if(c=='0'){
            r1[x] = '1';
            r2[x] = '9';
        }
        else if(c=='9'){
            r1[x] = '8';
            r2[x] = '0';
        }
        else{
            r1[x] = c+1;
            r2[x] = c-1;
        }
        return {r1, r2};
    }
    int openLock(vector<string>& deadends, string target) {
        for(auto& d:deadends){
            de[d] = 1;
        }
        if(de["0000"]){return -1;}
        queue<string> q;
        q.push("0000");
        int c = 0;
        while(q.size()){
            int t = q.size();
            while(t--){
                auto x = q.front(); q.pop();
                if(x==target){return c;}
                for(int i = 0; i<4; ++i){
                    auto [p1, p2] = neighbor(x, i);
                    if(!vis[p1] && !de[p1]){
                        vis[p1] = 1;
                        q.push(p1);
                    }
                    if(!vis[p2]&& !de[p2]){
                        vis[p2] = 1;
                        q.push(p2);
                    }
                }
            }
            c++;
        }
        
        return -1;
    }
};

#### AC Code [Dijkstra]
當然，單源最短路徑問題，還是可以使用較為泛用的演算法。Dijkstra在權值不為負值的時候都能在$O(E + VlogV)$求得最短路徑。但顯然地，Dijkstra會比前面上述兩種的複雜度還要高，因此用string作為key時(開一大堆Maps)，會被卡常數(超笨)。在下面的程式碼中還是能AC的，但要把key換為int。

#define P pair<int,int>
#define vt vector
class Solution {
public:
    set<int> de;
    pair<int,int> neighbor(int a, int x){
        string s = to_string(a);
        while(s.size()<4){
            s.insert(s.begin(), '0');
        }
        string r1, r2;
        r1 = r2 = s;
        char c = s[x];
        if(c=='0'){
            r1[x] = '1';
            r2[x] = '9';
        }
        else if(c=='9'){
            r1[x] = '8';
            r2[x] = '0';
        }
        else{
            r1[x] = c+1;
            r2[x] = c-1;
        }
        return {stoi(r1), stoi(r2)};
    }
    int openLock(vector<string>& deadends, string target) {
        const int mxN = 1e9+7;
        for(auto e:deadends){
            de.insert(stoi(e));
        }
        if(de.count(0)){return -1;}
        priority_queue<P, vt<P>, greater<P>> pq;
        int n = 1e4;
        vt<int> vis(n, 0);
        vt<int> dis(n, mxN);
        int t = stoi(target);
        dis[t] = 0;
        pq.push({0, t});
        while(pq.size()){
            auto [mn, mnI] = pq.top(); pq.pop();
            if(vis[mnI]){continue;}
            vis[mnI] = 1;
            vt<int> nxt;
            for(int i = 0; i<4; ++i){
                auto [p1, p2] = neighbor(mnI,i);
                if(!de.count(p1)){nxt.push_back(p1);}
                if(!de.count(p2)){nxt.push_back(p2);}
            }
            for(auto& e:nxt){
                
                int u = mnI, v = e, w = 1;
                if(dis[v]>dis[u]+w){
                    dis[v] = dis[u]+w;
                    pq.push({dis[v], v});
                }
            }
        }
        return dis[0]==mxN?-1:dis[0];
    }
};

### 4. Find the duplicate number
Leetcode - 287. Find the Duplicate Number
題目：N個大的數組，裡面元素為值為[1, N]。但數組中，有一個數重複了，找出他。
題解：
假設數組為 [1, 2, 3, 4, 5]，那對於所有i，都恰有i個數小於等於i，否則，重複數可能出現在1~i中(折半

:::danger
此處就是一個可能不一定適用於CP的trick。當我們給出hashing的方法時，通常不是面試官想看到的。
:::

### 5. 最少次數區間更新，使數組變為0
問題：一個數組$A, a_i \le 0, \forall a_i \in A$。每次更新操作，可以使區間$[i, j], i\le j \le n$的數值減1，求最少次能將數組所有數值變為0的次數。
題目：
[3229. Minimum Operations to Make Array Equal to Target](https://leetcode.com/problems/minimum-operations-to-make-array-equal-to-target/description/)
[1526. Minimum Number of Increments on Subarrays to Form a Target Array](https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/description/)
題解：把圖畫出來之後，有很直觀的解法。
如圖，我們很直觀的要把凸出來的部分，一層一層壓下去，這樣總共壓下去的距離會最短。
圖中，紅色和粉色的線段代表要壓下去的部分(最佳的壓法)。經過觀察可以發現，紅色和粉色的線段之總和，就是整個高度數組的上升部分的總和。因此，此題的答案可以直接等於**元素上升的總和**

### 6. One to one hashing
給一個字串$s$，經過轉換後，能否轉為$t$，轉換過程為對於給一個字符，可以轉換為另一個，但其關係必須為一對一。 (在這個設定下，若$s$能轉成$t$，那$t$必能轉成$s$)
題目：
- 205. Isomorphic Strings
- 290. Word Pattern