---
# System prepended metadata

title: LeetCode Algorithm 整理

---

# LeetCode Algorithm 整理
## Sliding Window

![](https://hackmd.io/_uploads/S1BWxQYnn.png)

[https://youtu.be/GcW4mgmgSbw](https://)
* 簡介： 在容器中一個固定大小的區段(window)，要持續位移時使用
* 原理： 假設容器大小為n，區段大小為k。區段要位移，只需減去initial value，加上next value(不必重新計算整個區段)
* brute-force的複雜度是O(n*k)
```
for(int i=0;i<n;i++){
    for(int j=i;j<i+k;j++){
    ...
    }
}
```
* sliding window的複雜度是O(n)
```
for(int i=k;i<nums.size();i++){
    sum=sum+nums[i]-nums[i-k];
}
```
### 難題解析1
![](https://hackmd.io/_uploads/Skq2Mzc32.png)
```
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l{},r{};
        while(r<nums.size()){
            if(nums[r]==0)k--;
            if(k<0){
                if(nums[l]==0)k++;
                l++;
            }
            r++;
        }
        return r-l;
    }
};
```
#### 解法：
兩個指標l與r都從index 0開始，l做為起點，r會一路跑到最後一個element。
當r遇到0時，則k-1，k可能變成負的。
當發現k是負的時，起點l需要往前移動一位(意思是透過讓window減少一位，來空出位子給多出來新的那一位)，如果l減少的那一格剛好==0，那原本用來讓那個0變1的k會多出來，則補上k++
#### 疑問：
Q：return的是r-l，但r一定會跑到終點，萬一longest Ones不在最後面，出來的結果怎麼還是對的?
A：window在往右移動的過程中，不會一直包含solution，只會維持最大可行解的寬度，並持續追蹤是：否有其他1's可以加入，讓最大寬度增加。
#### 補充：
```
int l{},r{};//將l、r的初始值設為0
```
### 難題解析2
> 這題狗幹難的，看了解說還是想很久才懂

![](https://hackmd.io/_uploads/SJwxXAih2.png)
[https://youtu.be/jSto0O4AJbM](https://)
#### 解法：
這題除了要用到window還要用到hash map(是我一開始沒想到的)，一共需要2個map
EX. 
Input: s = "ADOBECODEBANC", t = "ABC"

map1:    window    (紀錄目前window有幾個我們需要找的char)
| 種類(char) | 數量(int) | 
| -------- | -------- | 
| A    | 0     |
| B    | 0     |
| C    | 0     |

map2     count_t    (紀錄各個字元總共需要幾個)

| 種類(char)  | 數量(int)  |
| -------- | -------- |
| A    | 1     |
| B    | 1     |
| C    | 1     |

變數need是總共要幾種char，have是目前滿足幾種(那一種char要達到正確數量才算)
一樣需要pointer L和R來標示window範圍，L,R都從0起始，R最後會跑到終點
1. 當R指到其中一個我們要找的char時，在window裡的相對位子+1
2. 若window中該char數量達標，則have++，代表滿足了一個項目
3. 若滿足了have == need，先更新result，然後開始讓L往右移動，扣掉多餘的char，直到扣掉了一個我們要找的目標char為止，使have == need不成立
4. 接著再持續讓R移動，直到再次滿足have == need，(重複1~4)
複雜度是O(n)
```
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int>window,count_t;
        int L=0,R=0;
        pair<int,int> result(0,0);//紀錄找到的解的L,R分別是什麼
        int result_len=99999;//先設一個大一點的數
        for (char c : t) {
            count_t[c]++;//初始化 cout_t
        }
        int have=0, need=count_t.size();
        while(R<s.length()){
            char c=s[R];
            if(count_t.find(c) != count_t.end()){
                window[c]++;
                if( window[c] == count_t[c]){
                    have++;
                }
            }
            while( have == need){
                //update our result
                if(R-L+1 < result_len){
                    result.first=L;
                    result.second=R;
                    result_len=R-L+1;
                }
                //pop off the left of our window
                if(count_t.find(s[L]) != count_t.end()){
                    window[s[L]]--;
                    if(window[s[L]] < count_t[s[L]]){
                        have--;
                    }
                }
                L++;
            }
            R++;
        }
        cout<<result.first<<endl;
        if(result_len==99999)return "";
        else return s.substr(result.first,result_len);
    }
};

```


---

## Hash Map
* 簡介：當遇到有一連串資料需要儲存並反覆查詢時使用
* 原理：由於hash map查詢的複雜度是O(n)，在有需要大量查詢時，節省時間
* 補充：針對string的處理有時可以善用hash map，效率會提升很多。常見處理是26個英文字母各自作為一個key值，value則是記錄該字母在string中出現幾次 (由於字母只會有26種，這邊可以不宣告map，直接宣告成大小是26的陣列就好)

### 難題解析
![](https://hackmd.io/_uploads/BydcwLJph.png)
* 解法：首先需要一個map分別儲存key: vector<int>及value: vector<string>。
    strs中的每個string都用一個array(count)去紀錄它各個char出現幾次，由於同個group的string他們的count會相等，就以count作為key值，將string塞入value值(vector<string>)中，輸出時把map中的value通通塞進result vector再return就好。
* 分析：這裡演算法的時間複雜度是O(m*n)，m是每個string的平均大小、n是string的總量。
    有另一種做法是把每個string先按照a~z排序，由於排序的複雜度是O(nlog(n))，整體的複雜度成O(m*n*log(n))
    
```
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>>result;
        map<vector<int>,vector<string>>strs_mp;
        for(string str:strs){
           vector<int>char_count(26,0);
           for(char c:str){
               char_count[c-'a']++;
           }
           strs_mp[char_count].push_back(str);
        }
        for(auto it:strs_mp){
            result.push_back(it.second);
        }
        return result;
    }
};
```
* 補充：
vector的初始化 `vector<int>v(幾個元素,初始化為什麼值)`
透過char - 'a'來取的acsii值，a=0,b=1,...,z=25
    


---
## BackTracking
* 簡介：當要求的解沒辦法一眼看出，需要反覆"遞迴"找出所有解的時候使用
* 原理：固定格式通常會是在主要function中，呼叫一個backtrack function
    backtrack function會有迴圈不斷遞迴直到找完所有解
    backtrack 的過程中不太會需要return，需要傳遞的值都直接放在parameter中傳遞
    記得要在遞迴時設好條件限制，不成立的情況就不繼續往下遞迴
    
### 難題解析
![](https://hackmd.io/_uploads/BJHoh9Jph.png)

* 解法：首先要考慮遞迴時的條件，什麼時候代表找到解了，什麼時候代表不可能有解
    接著透過一個for loop從 candidates 的頭開始，candidates中每個數都會拿來當可能的組合(cur_comb)的首個數字(除了重複的數 會導致有重複的組合)
    找到首個數字後會再重複呼叫backtrack func，每次呼叫就會往目前的組合新增一個數，直到目前組合剛好滿足條件，或確定無法達到條件。
* 分析：在這題的backtracking中，時間複雜度是O (2^n)，因為對每個數字都有選或不選兩種可能，最糟的情況是全部列出，也就是 (2^n )。
```
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(),candidates.end());
        vector<int>temp;
        backtrack(result,candidates,temp,target,0);
        
        return result;
    }
    void backtrack(vector<vector<int>>& result,vector<int> candidates,vector<int> cur_comb,int target,int pos){
        if(target==0){
            result.push_back(cur_comb);
            return;
        }
        if(target<=0){
            return;
        }
        int prev=-1;
        for(int i=pos;i<candidates.size();i++){
            if(prev==candidates[i]){
                continue;
            }
            cur_comb.push_back(candidates[i]);
            backtrack(result,candidates,cur_comb,target-candidates[i],i+1);
            cur_comb.pop_back();
            prev=candidates[i];
        }
    }
};
```

    
    


---
## Binary Tree
* 簡介：處理binary tree的各種操作
* 原理：解這類的題需要的能力
    1.基本資料結構(常常需要選擇一種主要資料結構，選對就容易解)
    2.各種Traversal
    3.pointer運用
### 難題解析
    


---
## Kadane's Algorithm
* 簡介：
    
    
    


---
## Dynamic Programming
* 簡介：透過記錄目前計算的結果，讓後面變好算
* 原理：是一種divide and conquer，通常需要宣告出一個陣列，關鍵是要思考存什麼資料會有幫助。
    
### 難題解析：
> 這題一開始想錯方向，只要return true or false的話，判斷到不到的了終點就好
    
![](https://hackmd.io/_uploads/rJygK6nah.png)

* 解法： dp 要記錄的就是在s中，找到Dict中的字串後，接續起來能到達的位子。
dp是一個比s大1單位大小的bool array，多出來的一單位是起始位子，只要是Dict中的字串能到的地方，那裏的dp設為1。
迴圈的地方用兩層for，對於每個i為起始位子、j為尾端。去找是否符合dict中的字串
* 分析：
    
```
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        size_t n=s.length();
        vector<bool> dp(n+1,0);
        dp[0]=1;
        set<string>dict(wordDict.begin(),wordDict.end());
        for(size_t i=1;i<=n;i++){
            for(size_t j=0;j<i;j++){
                if( dp[j] && dict.find(s.substr(j,i-j))!=dict.end()){
                    dp[i]=1;
                    break;
                }
            }
        }
        return dp[n];
    }
};
```
