# LeetCode Algorithm 整理
## Sliding Window
[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
```
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://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的陣列就好)
### 難題解析
* 解法：首先需要一個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中傳遞
記得要在遞迴時設好條件限制，不成立的情況就不繼續往下遞迴
### 難題解析
* 解法：首先要考慮遞迴時的條件，什麼時候代表找到解了，什麼時候代表不可能有解
接著透過一個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的話，判斷到不到的了終點就好
* 解法： 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];
}
};
```
Sign in with Wallet
Connect another wallet