算法工程師思維導圖 | 數據結構與算法

賣萌屋的妹子們（劃掉）作者團整理的算法工程師思維導圖，求職/自我提升/查漏補缺神器。該手冊一共分為數據結構與算法、數學基礎、統計機器學習和深度學習四個部分。

點擊這裡查看具體使用指南。該手冊有兩種獲取方式：

下面是數據結構與算法部分~

數據結構

二維矩陣/直方圖最大距形面積

矩陣最大面積：https://leetcode-cn.com/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode/

直方圖dp

最小棧

https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/

LRU：雙向鍊表

https://leetcode-cn.com/problems/lru-cache/Least Recently Used

尋找重複數-環的入口

https://leetcode-cn.com/problems/find-the-duplicate-number/

快慢指針，相遇後，從頭髮起一個指針，按相同速度走，相遇即使環的入口

併查集

http://www.cnblogs.com/cyjb/p/UnionFindSets.html

字節跳動大闖關

https://blog.csdn.net/sinat_27705993/article/details/82053102

求不同併查集的個數 多一個count，每union一次count就減1

島嶼個數

https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/

多開一個放0的島

  前序：= 自頂向下

curr=stack.pop()
print(curr.val)
stack.push(curr.right)
stack.push(curr.left)
中序：加一個記錄
 curr = stack.pop()
   if curr in cache:
     res.append(curr.val)
     continue 
   cache.add(curr)
   stack.append(curr.right)
   stack.append(curr)
   stack.append(curr.left)
後序：同中序 = 自底向上
二叉樹的最近公共祖先
三個條件滿足兩個就是True：1.左子樹包含p1或p2 2.右子樹包含p1或p2 3.自己是p1或p2
二分查找樹
AVL：https://mp.weixin.qq.com/s/dYP5-fM22BgM3viWg4V44A
為啥有了BST和AVL還需要紅黑樹？https://zhuanlan.zhihu.com/p/72505589
AVL每次進行插入/刪除節點的時候，幾乎都會破壞平衡樹的第二個規則，進而我們都需要通過左旋和右旋來進行調整，使之再次成為一顆符合要求的平衡樹 如果在那種插入、刪除很頻繁的場景中，平衡樹需要頻繁著進行調整，這會使平衡樹的性能大打折扣，為了解決這個問題，於是有了紅黑樹
二叉樹中的最大路徑和
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
完全二叉樹插入
https://blog.csdn.net/psc0606/article/details/48742239
利用完全二叉樹的性質，找到要插入的位置，先判斷左子樹的最右結點與右子樹的最右結點高度，如果相等，只需要插入到左子樹即可，否則插入右子樹
完全二叉樹節點數
https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/er-fen-cha-zhao-by-xu-yuan-shu/
連續子數組和為k的倍數
https://leetcode-cn.com/problems/continuous-subarray-sum/solution/lian-xu-de-zi-shu-zu-he-by-leetcode/
和為K的子數組
https://leetcode-cn.com/problems/subarray-sum-equals-k/
連續區間和為K，用字典存儲累計和
求最長非重複字符串長度
https://blog.csdn.net/zd_nupt/article/details/82669299
做個hash_table表，記錄每個字符的位置。碰到重複的就求兩個重複字符之間的距離
查找
查找最小值/翻轉點 只判斷mid-right是否被翻轉
查找固定target 1.判斷mid-right是否被翻轉，找到升序的方向 2.跟升序區間的left/right和mid比看在不在，不在就搜索另一個空間
存在重複，尋找最小值 當num[mid]==num[right]時，right-=1 因為左閉右開，mid和right中存在別的值 [0,1,1,1] [1,1,0,1] [1, 0, 1, 1, 1] [1, 1, 1, 1] 特殊情況下時間複雜度為O(N)
bug-free寫法：左閉右開，先寫排除中位數的邏輯
https://www.zhihu.com/question/36132386/answer/97729337 lower/upper bound
尋找峰值
左閉右開，往高的地方走https://leetcode-cn.com/explore/learn/card/binary-search/210/template-ii/841/
尋找重複數
https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode/
雙數組中位數
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
找出第K小的距離對
https://leetcode-cn.com/problems/find-k-th-smallest-pair-distance/solution/hei-ming-dan-zhong-de-sui-ji-shu-by-leetcode/
二分查找 + 雙指針
階乘函數後K個零
https://leetcode-cn.com/problems/preimage-size-of-factorial-zeroes-function/solution/jie-cheng-han-shu-hou-kge-ling-by-leetcode/
乘法表中第k小的數
https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/
給定高度m 、寬度n 的一張 m * n的乘法表，以及正整數k，你需要返回表中第k 小的數字。
迷宮中的最短路徑
https://blog.csdn.net/qq_28468707/article/details/102786710
字符串A和B的最小相似度
https://leetcode-cn.com/problems/k-similar-strings/solution/xiang-si-du-wei-k-de-zi-fu-chuan-by-leetcode/
抖音紅人
DFS：https://blog.csdn.net/anlian523/article/details/82557468
BFS：https://blog.csdn.net/u014253011/article/details/82556976
對於每個用戶，遍歷粉絲數（記錄visited）
八皇后
https://blog.csdn.net/handsomekang/article/details/41308993
一行一行依次遍歷(從上往下),決定放在哪列(從左往右),這樣就不用判斷行衝突,只需要判斷列衝突和主斜線副斜線衝突.
對角線=>斜率為1 => abs(A[i]-A[j])==abs(i-j)
全排列
https://leetcode-cn.com/problems/permutations/solution/
有重複數字的全排列 sort：https://leetcode-cn.com/problems/permutations-ii/
復原IP位址
https://blog.csdn.net/OneDeveloper/article/details/84946233
dfs，如果加完3個「.」了則判斷是否符合條件，否則繼續加（start，start+3）
連通島嶼個數
字節-部門合併：https://blog.csdn.net/zd_nupt/article/details/82669299
dfs：每次遍歷到1，則把聯通的島置為0
兩數之和
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leetco/
在已排序的數組中找到兩個數，和為target
雙指針暴力求解 n^2 字典求解 時間n，空間n
我們使用兩個指針，初始分別位於第一個元素和最後一個元素位置，比較這兩個元素之和與目標值的大小。如果和等於目標值，我們發現了這個唯一解。如果比目標值小，我們將較小元素指針增加一。如果比目標值大，我們將較大指針減小一。移動指針後重複上述比較知道找到答案。時間 n，空間1
數組中兩數相減的最大值
https://blog.csdn.net/fkyyly/article/details/83930343
非排序數組中兩個數相減（前面減後面）的最大值。i<j, max(a[i]-a[j])
if a[i]-a[j]>0: j++ else: i = j, j++
最小覆蓋子串
https://leetcode-cn.com/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-2/
和為K的子數組
https://blog.csdn.net/a546167160/article/details/94401251
當區間和等於target，再向後遍歷，可以i+或j+，但是j+可能會越界，因此選擇i+
乘積小於K的子數組
https://leetcode-cn.com/problems/subarray-product-less-than-k/solution/cheng-ji-xiao-yu-kde-zi-shu-zu-by-leetcode/
排序
插入排序：穩定
把後面的某個一次次插到前面，再管後面的，第一次確定的位置可能不是最終位置
冒泡排序：穩定
把某個確定好，再管其他的，第一次確定的位置是最終位置
快速排序
https://blog.csdn.net/qq_36528114/article/details/78667034
快排優化：
    1. 在個數小於N時使用插入排序
    3. 加入三取樣切分 //省去了對重複元素的比較，性能接近線性
歸併排序：穩定
原地歸併：直接把合適的片段swap過去
https://blog.csdn.net/xiaolewennofollow/article/details/50896881
兩個片段的交換需要三次逆轉：分別逆轉[1, i]和[i+1,n] 再逆轉[1, n]
大數據歸併應用較多
數組中的逆序對
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
區間和的個數在某個區間
https://leetcode-cn.com/problems/count-of-range-sum/
鍊表排序
https://www.cnblogs.com/TenosDoIt/p/3666585.html
https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
         https://www.cnblogs.com/fengziwei/p/7875355.html
動態規劃
編輯距離
https://zhuanlan.zhihu.com/p/80682302
最長回文子序列／子串
最長回文子序列：bbbab -> bbbb
https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dong-tai-gui-hua-si-yao-su-by-a380922457-3/
最長回文子串：bbbab -> bbbhttps://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/
1. 排序後求LCS，時間O(n^2)，空間O(n)2. dp[i]存儲A[:i]的LIS，每個i和前面的下標對比，時間O(n^2)，空間O(n) for j in [i-1, 0]: if A[j]<A[i]: dp[i] = max(dp[i], dp[j]+1)3. dp[i]存儲LIS為i+1時最大的值，最後len(dp)即為答案，時間O(nlogn)，空間O(n) 二分法查找插入dp的位置
最大子序和
最大和包含當前和不包含：sum[i] = max(sum[i-1]+a[i], a[i])
背包問題
https://blog.csdn.net/stack_queue/article/details/53544109
最短路徑
Dijkstra：單源&邊權非負
https://www.jianshu.com/p/ff6db00ad866
Floyd：全源&負環，任意兩點間的最短路徑，時間複雜度為O(N3)，空間複雜度為O(N2)
Bellmanford：單源
https://blog.csdn.net/lpjishu/article/details/52413812
Johnson：全源&非負環
股票問題
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/
模式匹配
單模式單匹配：KMP
字符串匹配，返回第一個匹配的位置
https://www.zhihu.com/question/21923021/answer/281346746
大數據
蓄水池抽樣法
選k個，新舊元素被選中第概率都是k/n 第k+1個以k/(k+1)被選中，之前在水池裡的被替換概率為k/(k+1)*1/k=1/(k+1) 則舊元素留下的概率為k/(k+1)，與新元素相等。