數(shù)組篇

1. 二分法：

1. 寫程序的時候，一般會用左閉右閉區(qū)間脖阵，或者左閉右開區(qū)間。

左閉右閉：while left <= right:? ? ? ? ? ? ?right = middle -1?

左閉右開： while left < right:? ? ? ? ? ? ? right = middle （反正取不到right）

2. 移除元素

數(shù)組的元素在內(nèi)存地址中是連續(xù)的，不能單獨刪除數(shù)組中的某個元素蔫仙，只能覆蓋哀卫。

題目：給你一個數(shù)組 nums?和一個值 val巨坊，你需要 原地 移除所有數(shù)值等于?val?的元素。

這題可以用快慢指針此改，等于val的快指針多走一步趾撵，然后用快指針的值覆蓋慢指針的值。

3. 滑動窗口

滑動窗口解法：其實就是用一個循環(huán)來做兩個for循環(huán)的事情共啃。left等價于控制開始位置的for循環(huán)占调，right等價于控制結(jié)束位置的for循環(huán)。

鏈表篇：

1.?移除鏈表元素（虛擬頭結(jié)點）

題目：給定一個鏈表和一個值移剪，將鏈表中與值相等的節(jié)點刪除究珊。

因為刪除頭結(jié)點和其他節(jié)點的方式不同。導(dǎo)致代碼不統(tǒng)一纵苛。加入一個虛擬頭結(jié)點后剿涮，頭結(jié)點就和其他節(jié)點一樣了，就可以用統(tǒng)一的代碼處理攻人。

2.?反轉(zhuǎn)鏈表類

題目：把一個列表翻轉(zhuǎn)取试。

用prev current兩個指針來實現(xiàn)。自己畫圖把邏輯理清楚怀吻，然后寫一遍就好瞬浓。

題目：將相鄰的節(jié)點兩兩交換

這就比反轉(zhuǎn)列表更提高難度了。要用更多個指針烙博。還是一樣瑟蜈，自己畫圖把邏輯理清楚烟逊，然后寫一遍就好。

3. 鏈表相交&環(huán)形

題目：給出兩個單鏈表的頭結(jié)點铺根，返回他們的相交節(jié)點宪躯。

既然相交，那尾部應(yīng)該是一樣的位迂。那就求出兩個鏈表的長度访雪。求長度差N，長鏈表先走N步后掂林，短鏈表的指針也出發(fā)臣缀。兩指針相遇的點就是交點。

題目：判斷鏈表是否有環(huán)泻帮。如果有環(huán)返回環(huán)的入口精置。

思路，創(chuàng)造一個兩指針相遇在環(huán)入口節(jié)點的機會锣杂！

假設(shè)入口節(jié)點為x, 入環(huán)后再走y個點脂倦，快慢指針相遇，y再走z步又到入口節(jié)點x元莫。則我們有2(x+y) = x + n(y+z) + y => x = (y+z) - y

這意味著赖阻，如果有個新指針2, 在環(huán)內(nèi)先走了y步，然后另個一個指針1從head出發(fā)踱蠢，兩指針都走x步的時間火欧，將會在環(huán)的入口相會。這就創(chuàng)造出了指針相等的條件茎截。

哈希表篇

當(dāng)我們遇到了要快速判斷一個元素是否出現(xiàn)集合里的時候苇侵，就要考慮哈希法。

題目：兩個單詞稼虎，判斷是否由相同的字母構(gòu)成衅檀。

用一個字典統(tǒng)計字母頻數(shù)即可。這里需要記住一個ord(）函數(shù)

題目：兩數(shù)相加

給定一個整數(shù)數(shù)組 nums?和一個目標(biāo)值 target霎俩，請你在該數(shù)組中找出和為目標(biāo)值的那?兩個?整數(shù)哀军，并返回他們的數(shù)組下標(biāo)。

用字典儲存打却。遍歷一遍杉适，如果num的補數(shù)（target - num）在字典內(nèi)，則返回他們的數(shù)組下標(biāo)柳击。不在猿推，就把num和對應(yīng)的下標(biāo)計入字典。

題目：三數(shù)之和?

給定一個長度超過3的數(shù)組，返回所有的三數(shù)組合 [nums[i], nums[j], nums[k]]?such that?i != j,?i != k, and?j != k, and?nums[i] + nums[j] + nums[k] == 0. 答案中不含重復(fù)的三數(shù)組合蹬叭。

排序后藕咏，最外層的循環(huán)是第一個數(shù)。然后在區(qū)間[i, n-1]里面用雙指針秽五，left, right孽查。找三數(shù)之和為0.

題目：四數(shù)之和?I

將上一題的三數(shù)之和拓展為四數(shù)之和。三數(shù)組合是一層for循環(huán)坦喘，加一層左右指針盲再。四數(shù)組合可以兩層for循環(huán)，加一層左右指針瓣铣。

題目：四數(shù)相加II

給定四個包含整數(shù)的數(shù)組列表?A , B , C , D ,計算有多少個元組 (i, j, k, l)?答朋，使得?A[i] + B[j] + C[k] + D[l] = 0。

和兩數(shù)之和類似棠笑。AB相加的和放入一個set梦碗，然后計算-(C+D)看是否在set中。

字符串篇

1. 反轉(zhuǎn)字符串

題目：將輸入的字符串反轉(zhuǎn)過來蓖救。你必須原地修改輸入數(shù)組叉弦、使用 O(1) 的額外空間解決這一問題。

左右指針對應(yīng)值互換即可

題目：給定一個字符串 s 和一個整數(shù) k藻糖，從字符串開頭算起, 每計數(shù)至 2k 個字符，就反轉(zhuǎn)這 2k 個字符中的前 k 個字符库车。

定義一個翻轉(zhuǎn)的函數(shù)巨柒，然后逐一處理每一段2k個字符。

2.?全部翻轉(zhuǎn)+局部翻轉(zhuǎn)

題目：給定一個字符串柠衍，逐個翻轉(zhuǎn)字符串中的每個單詞洋满。

沒啥把句子里的單詞翻轉(zhuǎn)的方法。那就把整個字符串全部翻轉(zhuǎn)珍坊，然后每個單詞內(nèi)部翻轉(zhuǎn)回去牺勾。

題目：右旋轉(zhuǎn)字符串：給定一個字符串 s 和一個正整數(shù) k，將字符串中的后面 k 個字符移到字符串的前面阵漏。

先這個字符串全部翻轉(zhuǎn)驻民，然后局部翻轉(zhuǎn)：前k個字符翻轉(zhuǎn)，剩下的翻轉(zhuǎn)履怯。

棧與隊列篇

1. 棧和隊列的相互轉(zhuǎn)換

題目：用棧實現(xiàn)隊列

思路：用兩個棧實現(xiàn)隊列回还。stack1存入，要pop前先轉(zhuǎn)移元素到stack2, 此時stack2就類似隊列了叹洲；接著把stack2棧頂?shù)脑貜棾黾纯赡丁Ｗ⒁猓涸趕tack2清空前（也就是隊列前面部分耗光前），不需要再做移動的操作运提。

題目：用隊列實現(xiàn)棧

思路：用兩個隊列實現(xiàn)棧蝗柔。q1存入闻葵。如果要彈出，就把q1元素移動到q2癣丧，然后剩最后一個元素槽畔，彈出。注意：移動完后坎缭，直接把q1 q2互換竟痰，不需要移回來。因為兩個隊列順序都一樣掏呼。

2. 棧的應(yīng)用

題目：給定一個只包括 '('坏快，')'，'{'憎夷，'}'莽鸿，'['，']'?的字符串拾给，判斷字符串是否合法祥得。

思路：用字典把左右括號對應(yīng)起來。碰到左括號入棧蒋得，右括號出棧级及。

題目：給出由小寫字母組成的字符串?S，重復(fù)項刪除操作會選擇兩個相鄰且相同的字母额衙，并刪除它們饮焦。

碰到與棧頂元素不一樣的就入棧，碰到一樣的就彈出窍侧。最后返回棧這個列表組成的字符串即可县踢。

題目：逆波蘭表達(dá)式求值

思路：碰到數(shù)字存入棧；碰到符號則彈出棧頂?shù)膬蓚€元素伟件，運算后的結(jié)果存入棧

3. 最小堆的應(yīng)用

題目：給定一個非空的整數(shù)數(shù)組硼啤，返回其中出現(xiàn)頻率前 k 高的元素。

思路：1. 要統(tǒng)計元素出現(xiàn)頻率：用map統(tǒng)計頻率斧账；2. 對頻率排序谴返，用大頂堆排序；3. 找出前K個高頻元素咧织。

題目：給定一個數(shù)組 nums亏镰，有一個大小為?k?的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。返回滑動窗口中的最大值拯爽。

思路：其實隊列沒有必要維護窗口里的所有元素索抓，只需要維護有可能成為窗口里最大值的元素就可以了。移動窗口時候，是根據(jù)index移除逼肯，因此窗口里也維護index就好了嬉探。

二叉樹篇

深度優(yōu)先：前中后序遍歷魏宽； 廣度優(yōu)先：層序遍歷。要熟練掌握遞歸迭代的方法。

1.? 求二叉樹的屬性

題目：給定一個二叉樹甫窟，檢查它是否是鏡像對稱的删性。

思路：1. 遞歸法：終止條件：if 左右都為空庆械，對稱津肛，返回true；elif 有一個為空搜锰，不對稱伴郁，return false；elif 左右都有值蛋叼，但值不等焊傅，不對稱 return false。遞歸條件：else 比較 left.left vs right.right 和 left.right vs right.left.

題目：二叉樹的最大深度狈涮。 & n叉樹的最大深度狐胎。

思路：迭代法：層序遍歷。遞歸法歌馍，前序遍歷握巢。

題目：給定一個二叉樹，找出其最小深度松却。最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量镜粤。

思路：遞歸：終止條件：碰到葉節(jié)點則返回1. 遞歸條件：返回左子樹（如果有）和右子樹（如果有）的最小深度，取較小者玻褪。

題目：完全二叉樹的節(jié)點個數(shù)

思路：完全二叉樹只有兩種情況，1：就是滿二叉樹公荧，2：最后一層葉子節(jié)點沒有滿带射。但左子樹或右子樹一定有一個滿二叉樹。

對于情況一循狰，可以直接用 2^樹深度 - 1 來計算窟社。對于情況二，左右孩子中绪钥，滿二叉樹的那個直接計算灿里。而另一個進行遞歸。

題目：給定一個二叉樹程腹，判斷它是否是高度平衡的二叉樹匣吊。

思路：一棵高度平衡二叉樹定義為：一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過1。

遞歸法：終止條件：如果根節(jié)點為空，返回True色鸳；如果左右子樹高度差超過1社痛，就返回False。遞歸條件：遞歸左右子樹命雀。迭代法一樣蒜哀。

題目：給定一個二叉樹，返回從根節(jié)點到葉子節(jié)點的所有路徑吏砂。葉子節(jié)點是指沒有子節(jié)點的節(jié)點撵儿。

思路：需要記錄路徑，回溯算法最合適狐血。

題目：計算給定二叉樹的所有左葉子之和淀歇。

思路：要注意是判斷左葉子，不是二叉樹左側(cè)節(jié)點氛雪，所以不要上來想著層序遍歷房匆。簡單的前序遍歷即可。左葉子三個約束條件：1. 不是根節(jié)點 2. 是葉節(jié)點 3. 是父節(jié)點的左節(jié)點报亩。 迭代的時候浴鸿，根節(jié)點以下，把節(jié)點放入stack的時候弦追，帶上一個標(biāo)簽表示是否是左節(jié)點岳链。

題目：給定一個二叉樹，在樹的最后一行找到最左邊的值劲件。

思路：用層序遍歷是非常簡單的了掸哑，反而用遞歸的話會比較難一點。

這里的層序遍歷零远，在每一層內(nèi)部從右到左苗分，保證最后一個節(jié)點是最左的節(jié)點。

題目：給定一個二叉樹和一個目標(biāo)和牵辣，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑摔癣，這條路徑上所有節(jié)點值相加等于目標(biāo)和。112返回布爾值纬向，113返回所有符合的路徑择浊。

思路：終止條件：到葉節(jié)點的時候，看路徑上所有節(jié)點的值總和是否等于targetSum逾条。如果相等琢岩，就把路徑貼入結(jié)果。如果不是葉節(jié)點师脂，就繼續(xù)放進棧迭代担孔。

2. 二叉樹的修改與構(gòu)造

題目：翻轉(zhuǎn)一棵二叉樹江锨。

思路：只要把每一個節(jié)點的左右孩子翻轉(zhuǎn)一下，就可以達(dá)到整體翻轉(zhuǎn)的效果攒磨。

這道題目使用前序遍歷和后序遍歷都可以泳桦，唯獨中序遍歷不方便，因為中序遍歷會把某些節(jié)點的左右孩子翻轉(zhuǎn)了兩次娩缰！

題目：中序+前/后序 構(gòu)造二叉樹

思路：前序遍歷第一個元素是根灸撰，后序遍歷最后一個元素是根，中序遍歷根元素左邊是左子樹拼坎，右邊是右子樹浮毯。

題目：給定一個不含重復(fù)元素的整數(shù)數(shù)組。構(gòu)建最大二叉樹

思路：最大二叉樹的根是數(shù)組中的最大元素泰鸡。左子樹是通過數(shù)組中最大值左邊部分構(gòu)造出的最大二叉樹债蓝。右子樹是通過數(shù)組中最大值右邊部分構(gòu)造出的最大二叉樹。與上一題一樣盛龄。

題目：合并二叉樹?饰迹。合并的規(guī)則是如果兩個節(jié)點重疊，那么將他們的值相加作為節(jié)點合并后的新值余舶，否則不為?NULL 的節(jié)點將直接作為新二叉樹的節(jié)點啊鸭。

思路：遞歸法終止條件：兩個root都為空，返回空匿值；一個為空赠制，返回另一個；遞歸條件：兩個都不為空挟憔，root.val等于兩個相加钟些，左右節(jié)點遞歸。

迭代法：層序遍歷比較方便绊谭。

3. 二叉搜索樹的屬性

題目：給定二叉搜索樹（BST）的根節(jié)點和一個值政恍。 你需要在BST中搜索到節(jié)點值等于給定值的節(jié)點。?

思路：二分搜索法

題目：給定一個二叉樹达传，驗證其是否是一個有效的二叉搜索樹篙耗。

思路：遞歸法和迭代法都很直觀，見代碼趟大。還有一種做法是：二叉搜索樹的中序遍歷是遞增序列（反之也成立）。

題目： 二叉搜索樹中節(jié)點值之間的最小絕對差?

思路：搜索二叉樹的中序遍歷是遞增數(shù)列铣焊。然后對遞增序列求最小絕對差逊朽。用callback: callback其實就是把函數(shù)diff()作為參數(shù)傳入中序遍歷函數(shù)inorder_traversal()。

題目：二叉搜索樹中的眾數(shù)?

思路：依然是利用中序遍歷轉(zhuǎn)為遞增數(shù)列曲伊。用callback把函數(shù)update_mode?作為參數(shù)傳入遍歷函數(shù)inorder_traversal()叽讳。

題目：把二叉搜索樹轉(zhuǎn)換為累加樹?追他，使每個節(jié)點 node?的新值等于原樹中大于或等于?node.val?的值之和。

思路：可以用右中左逆中序遍歷轉(zhuǎn)為遞減序列岛蚤。這樣只要從前往后累加就好了邑狸。

4. 二叉搜索樹的修改與構(gòu)造

題目：二叉搜索樹中的插入操作?

思路：遞歸：和二分法查找類似。迭代：稍微麻煩點涤妒，需要記錄父節(jié)點单雾，插入的方向，這樣才能做插入操作

題目：刪除二叉搜索樹中的節(jié)點?

思路：1. 在二叉搜索樹中找到該節(jié)點她紫。如果是葉節(jié)點硅堆，直接刪除；如果有一個左右節(jié)點贿讹，用左右子樹代替當(dāng)前節(jié)點渐逃；如果同時有左右節(jié)點，就去找右子樹的最小值民褂，把這個最小值填入當(dāng)前節(jié)點茄菊。然后在右子樹中，刪除最小值節(jié)點（一定是葉節(jié)點）赊堪。

用迭代法要注意面殖，如果刪除子節(jié)點，要更新父節(jié)點對其的引用雹食。因為二叉樹節(jié)點是一個對象實例畜普，而python 是沒有辦法立即釋放一個對象的。我們只可以通過修改 父節(jié)點的 left 或 right 指針來解除對子節(jié)點的引用群叶，而不能直接讓子節(jié)點等于None而實現(xiàn)刪除吃挑。

題目：給定最小邊界L 和最大邊界 R。通過修剪二叉搜索樹街立，使得所有節(jié)點的值在[L, R]中 (R>=L) 舶衬。

迭代法：用stack寫有些麻煩，可以利用二叉搜索樹的性質(zhì)赎离，最大和最小的節(jié)點都在最邊上逛犹，只要把最邊上超出范圍的節(jié)點修剪去即可，不比遍歷所有節(jié)點梁剔。不過這里最好用一個虛擬頭結(jié)點才好處理虽画。

遞歸法：如果當(dāng)前節(jié)點超出右邊界，就返回左節(jié)點荣病；如果超出左邊界码撰，就返回右節(jié)點；如果不超出邊界个盆，就對左右節(jié)點遞歸使用函數(shù)脖岛。

題目：從一個遞增數(shù)組朵栖，構(gòu)造一棵高度平衡二叉搜索樹。

思路：找出數(shù)組的中間節(jié)點為根節(jié)點柴梆。

5. 二叉樹公共祖先問題

?題目：二叉樹的最近公共祖先??

思路：遞歸法是最直觀的：

終止條件：找到等于p or 找到等于q or 找到None陨溅，都返回node.?

遞歸條件：遞歸每個node的left和right，如果left right都有返回绍在，則返回當(dāng)前Node门扇，如果只有l(wèi)eft有返回，則返回left的返回揣苏，如果只有right也一樣悯嗓。

題目：二叉搜索樹的最近公共祖先

思路：比普通二叉樹更容易。但要注意卸察，返回節(jié)點的終止條件是：min(p.val, q.val) <= root.val <= max(p.val, q.val)脯厨，要取等。因為如果遍歷到p或者q時候坑质，另一個node一定在其子樹上合武。

單調(diào)棧篇

通常一維數(shù)組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置涡扼，此時我們就要想到可以用單調(diào)棧了稼跳。時間復(fù)雜度為O(n)。

題目：根據(jù)每日溫度輸出：要想觀測到更高的氣溫吃沪，至少需要等待的天數(shù)汤善。

思路：使用一個從棧底到棧頂遞減的單調(diào)棧，while新元素 i 比棧頂?shù)脑卮笃北耄蔷蛷棾鰲ｍ斣豿红淡，那元素x距離第一個比自己大的元素就是 i-x.

題目：下一個更大元素 I

nums1?是?nums2?的子集（沒有重復(fù)元素）。找出 nums1?中每個元素在?nums2?中的下一個比其大的值降铸。

思路：和上一題幾乎一模一樣在旱，就不過把元素放到了nums1而已。

題目：下一個更大元素II

給定一個循環(huán)數(shù)組推掸，輸出每個元素的下一個更大元素桶蝎。

思路：還是單調(diào)棧的應(yīng)用。只要循環(huán)兩個數(shù)組長度即可谅畅。

題目：接雨水：給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖登渣，計算按此排列的柱子，下雨之后能接多少雨水毡泻。

接雨水這題本質(zhì)上是尋找左右第一個高于自己的柱子胜茧。用一個從棧低到棧頂遞減的單調(diào)棧即可。

那雨水面積就是?water += (i - stack[-1] - 1) * (min(right, left) - mid)牙捉。這里要注意竹揍，頭尾兩側(cè)沒有柱子圍著。如果stack pop到空邪铲，也就意味著此時沒有左柱子圍著了芬位。那就要break。

題目：柱狀圖中最大的矩形带到。給定 n 個非負(fù)整數(shù)昧碉，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰揽惹，且寬度為 1 被饿。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積搪搏。

單調(diào)棧思路：最大矩形實際上就是尋找左右第一個低于自己的柱子狭握。用一個從棧底到棧頂遞增的單調(diào)棧即可。

那矩形面積就是：(right-left-1)*heights[mid] 疯溺。不過這里要注意论颅，左右第一個柱子，沒有更左或更右的低于自身的柱子囱嫩。那就頭尾加兩個0好了恃疯。

回溯算法篇

代碼模板：

題目太多就不總結(jié)了∧校看文章第20-26天今妄。

以及卡哥總結(jié)?https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

貪心算法篇

看文章27-32。重點看31 32兩天鸳碧。

卡哥總結(jié)?https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html