經(jīng)驗(yàn)總結(jié)：
常用方法：
空間換時(shí)間法：開(kāi)辟新的數(shù)組去記錄信息
多索引方法：多指針、標(biāo)記定位+遍歷、碰撞指針、滑動(dòng)窗口
查表法
回溯法：
暴力搜索的實(shí)現(xiàn)手段；
for循環(huán)遍歷當(dāng)前的所有可能選項(xiàng)；
要么選擇，要么不選；
遞歸：
假設(shè)實(shí)現(xiàn)，找關(guān)系；
子函數(shù)遞歸，主函數(shù)調(diào)用子函數(shù)，以及主函數(shù)自身遞歸）
動(dòng)態(tài)規(guī)劃：
1.0-1背包問(wèn)題
2.要么選擇，要么不選
3.考慮從[0..n]并選中n
11 盛水容器
方法：碰撞指針
解題思路：
瓶頸在于高
注意left，right邊界的操作
13 羅馬數(shù)字轉(zhuǎn)整數(shù) **
方法：查表法
解題思路：
1.找到規(guī)律--數(shù)字的表達(dá)式？
2.逐個(gè)查表
實(shí)現(xiàn)：
寫(xiě)成了面向過(guò)程逐個(gè)if分支的程序，導(dǎo)致代碼比較冗長(zhǎng)
17 電話(huà)號(hào)碼組合
方法：回溯法
解題思路：
1.構(gòu)建字母表
2.設(shè)計(jì)回溯算法（通過(guò)遞歸子函數(shù)來(lái)實(shí)現(xiàn)，調(diào)用遞歸時(shí)通過(guò)一個(gè)for循環(huán)遍歷每一種可能的選擇）
19 刪除鏈表倒數(shù)第N個(gè)節(jié)點(diǎn)
方法：快慢指針?lè)?br>
解題思路：
設(shè)計(jì)2個(gè)指針，一個(gè)先走N步，然后下一個(gè)再開(kāi)始走，刪除用虛擬頭結(jié)點(diǎn)
20 有效的括號(hào)
方法：棧
解題思路：
根據(jù)入棧、出棧來(lái)判斷
21 合并兩個(gè)有序鏈表
方法：多指針?lè)?br>
解題思路：
設(shè)計(jì)多個(gè)指針，操作
22 括號(hào)生成 **
方法：回溯法
解題思路：
0.畫(huà)一個(gè)樹(shù)形圖，來(lái)判斷需要的變量
1.當(dāng)前操作要么生成（，要么生成）
2.我考慮的是用兩個(gè)變量來(lái)記錄左括號(hào)和右括號(hào)
class Solution {
public:
vector<string> generateParenthesis(int n) {
ret.clear();
getRet(0,0,n,"");
return ret;
}
private:
vector<string> ret;
void getRet(int left,int right,int n,const string temp){
if(left==n && right==n){
ret.push_back(temp);
return ;
}
if(left<n)
getRet(left+1,right,n,temp+'(');
if(left>right)
getRet(left,right+1,n,temp+')');
}
};
代碼實(shí)現(xiàn)：
用left，right2個(gè)變量去記錄左括號(hào)和右括號(hào)的數(shù)量，然后每次要么生成左括號(hào)，要么生成右括號(hào)，注意條件限制，首先左括號(hào)數(shù)量要保證多于右括號(hào)才能生右括號(hào)，其次左括號(hào)的數(shù)量不能超過(guò)n
24.兩兩交換鏈表中的節(jié)點(diǎn)
方法：多指針技術(shù)
解題思路：
把需要操作的節(jié)點(diǎn)用指針去標(biāo)記、追蹤，即可
26.刪除排序數(shù)組中的重復(fù)項(xiàng)
方法：多索引技術(shù)
解題思路：
設(shè)計(jì)2個(gè)索引，1個(gè)用來(lái)標(biāo)記位置cur，1個(gè)用來(lái)遍歷i
遍歷i指向的元素若符合條件，便放入cur標(biāo)記的位置
27.移除元素
方法：多索引技術(shù)（標(biāo)記定位+遍歷）
解題思路：
同上
39.組合總和 *
方法：回溯法
解題思路：
0.先畫(huà)樹(shù)形圖，判斷哪些是需要的
1.設(shè)計(jì)遞歸結(jié)構(gòu)，每次遞歸前用for去遍歷所有可能的選項(xiàng)
2.設(shè)計(jì)終止條件
經(jīng)驗(yàn)：
回溯算法的一個(gè)小技巧，是把需要維護(hù)的狀態(tài)變量作為形參去引用傳遞，這樣回溯時(shí)就可以不用維護(hù)了
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
ret.clear();
int n=candidates.size();
if(n==0)
return ret;
vector<int> temp;
getRet(candidates,target,0,0,temp);
return ret;
}
private:
vector<vector<int>> ret;
void getRet(vector<int>& candidates,int target,int index,int sum,vector<int>& temp){
if(sum==target){
ret.push_back(temp);
return ;
}
int n=candidates.size();
for(int i=index;i<n;i++){
if(sum+candidates[i]<=target){
temp.push_back(candidates[i]);
getRet(candidates,target,i,sum+candidates[i],temp);
temp.pop_back();
}
}
}
};
46.全排列
方法：
回溯法
解題思路：
同上
51.N皇后 *
方法：
回溯法
解題思路：
1.設(shè)計(jì)出對(duì)角線(xiàn)、副對(duì)角線(xiàn)的判斷方式
2.同上
經(jīng)驗(yàn)：
回溯法和遞歸設(shè)計(jì)有1個(gè)區(qū)別是回溯法是遍歷各種可能的選擇，然后去判斷；遞歸則類(lèi)似于數(shù)學(xué)歸納法，設(shè)計(jì)好出口，然后假設(shè)已經(jīng)完成該功能，然后向出口去迭代
66.加一 *
方法：
遞歸
解題思路：
大數(shù)加法：
1.基本操作
2.處理進(jìn)位
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
if(n==0) return digits;
int carr=1;
for(int i=n-1;i>=0;i--){
int d=digits[i]+carr;
digits[i]=d%10;
carr=d/10;
if(carr==0) break;
}
if(carr) digits.insert(digits.begin(),carr);
return digits;
}
};
代碼思路：
因?yàn)槭羌?，直接讓carry初值為1即可，沒(méi)必要拆分成2部分去驅(qū)動(dòng)（拆分是指先做一次加1，再討論）
69.求平方根 *
方法：
二分查找
牛頓迭代法
擴(kuò)展：
輾轉(zhuǎn)相除法求最大公約數(shù)
class Solution {
public:
int mySqrt(int x) {
if(x<2)
return x;
long long low=1L,high=(long long)x/2+1;
while(low<=high){
long long mid=(long long)low+(high-low)/2;
long long key=mid*mid;
if(key==x)
return mid;
else if(key<x)
low=mid+1;
else
high=mid-1;
}
return high;
}
};
現(xiàn)在有些搞不清楚二分查找法什么時(shí)候用等號(hào)了。。。
舉例子即可
70.爬樓梯
方法：
dp、遞歸、循環(huán)都可以
75.顏色分類(lèi)
方法：
桶排序？
77.組合
方法：
回溯法
78.子集 **
方法：
回溯法
解題思路：
0.畫(huà)樹(shù)形圖
1.要么選擇當(dāng)前元素，要么不選擇當(dāng)前元素
79.單詞搜索
方法：
回溯法
問(wèn)題拆解：
1.邊界判斷，是否越界
2.4個(gè)方向，用1個(gè)二維數(shù)組記錄，這樣可以通過(guò)for循環(huán)去遍歷
解題思路：
0.遍歷每個(gè)單元格
1.從單元格開(kāi)始查找
80.刪除數(shù)組重復(fù)元素II
方法：
多索引（標(biāo)記定位+遍歷）
88.合并兩個(gè)有序數(shù)組
方法：
開(kāi)辟新空間法
101.對(duì)稱(chēng)二叉樹(shù)
方法：
遞歸
102、104、111樹(shù)的問(wèn)題
方法：遞歸
112.路徑總和
方法：
遞歸（子函數(shù)遞歸，主函數(shù)調(diào)用子函數(shù)，以及主函數(shù)自身遞歸）
解題思路：
子函數(shù)遞歸，主函數(shù)調(diào)用子函數(shù)，以及主函數(shù)自身遞歸）
118、119.楊輝三角形 **
方法：
循環(huán)、記錄、空間換時(shí)間法
問(wèn)題拆分：
1.楊輝三角各行之間的關(guān)系（當(dāng)前行和上一行的規(guī)律）
解題思路：
記錄上一行
根據(jù)上一行計(jì)算出當(dāng)前行
迭代
121.股票買(mǎi)賣(mài)時(shí)機(jī) *
方法：
貪心？假設(shè)法
解題思路：
允許反悔，買(mǎi)高了允許反悔；漲價(jià)了，立馬收益（賣(mài)價(jià)-成本價(jià)）；多次求值取最大值
122.股票買(mǎi)賣(mài)時(shí)機(jī)II *
方法：
貪心？假設(shè)法
解題思路：
允許反悔，買(mǎi)高了允許成本降價(jià)；漲價(jià)了立馬收益（賣(mài)價(jià)-成本價(jià)；成本價(jià)更新為當(dāng)前賣(mài)價(jià)）；最終求和
136.找出只出現(xiàn)一次的數(shù)字
方法：
異或運(yùn)算，自己與自己異或?yàn)?；0與A異或得A
144、145樹(shù)的遍歷
方法：
1.遞歸
2.循環(huán)（用棧模擬） **
146.LRU算法 ***
方法：
雙向鏈表+hash表映射；頭、尾指針
148.鏈表排序 ***
方法：
遞歸（子函數(shù)遞歸or非遞歸實(shí)現(xiàn)+主函數(shù)調(diào)用子函數(shù)、主函數(shù)遞歸調(diào)用自身）
解題思路：
歸并排序：
1.分割鏈表
2.merge操作
