一.基本演算法:

列舉. (poj1753,poj2965)貪心(poj1328,poj2109,poj2586)遞迴和分治法.遞推.構造法.(poj3295)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)最小生成樹演算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026)拓撲排序 (poj1094)二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.資料結構.

串 (poj1035,poj3080,poj1936)排序(快排、歸併排(與逆序數有關)、堆排) (poj2388,poj2299)簡單並查集的應用.雜湊表和二分查詢等高效查詢法(數的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)哈夫曼樹(poj3253)堆trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜尋

深度優先搜尋 (poj2488,poj3083,poj3009,poj1321,poj2251)廣度優先搜尋(poj3278,poj1426,poj3126,poj3087.poj3414)簡單搜尋技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

揹包問題. (poj1837,poj1276)型如下表的簡單DP(可參考lrj的書 page149): E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)

六.數學

組合數學: 1.加法原理和乘法原理. 2.排列組合. 3.遞推關係. (POJ3252,poj1850,poj1019,poj1942)數論. 1.素數與整除問題 2.進位制位. 3.同餘模運算. (poj2635, poj3292,poj1845,poj2115)計算方法. 1.二分法求解單調函式相關知識.(poj3273,poj3258,poj1905,poj3122)

七.計算幾何學.

幾何公式.叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)(poj1408,poj1584)凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:一.基本演算法:

C++的標準模版庫的應用. (poj3096,poj3007)較為複雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)最小費用最大流(poj2516,poj2516,poj2195)雙連通分量(poj2942)強連通分支及其縮點.(poj2186)圖的割邊和割點(poj3352)最小割模型、網路流規約(poj3308)

三.資料結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)靜態二叉檢索樹. (poj2482,poj2352)樹狀樹組(poj1195,poj3321)RMQ. (poj3264,poj3368)並查集的高階應用. (poj1703,2492)KMP演算法. (poj1961,poj2406)

四.搜尋

最最佳化剪枝和可行性剪枝搜尋的技巧和最佳化 (poj3411,poj1724)記憶化搜尋(poj3373,poj1691)

五.動態規劃

較為複雜的動態規劃(如動態規劃解特別的旅行商TSP問題等) (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學: 1.容斥原理. 2.抽屜原理. 3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).4.遞推關係和母函式.數學. 1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222) 2.機率問題. (poj3071,poj3440) 3.GCD、擴充套件的歐幾里德(中國剩餘定理) (poj3101)計算方法. 1.0/1分數規劃. (poj2976) 2.三分法求解單峰(單谷)的極值. 3.矩陣法(poj3150,poj3422,poj3070) 4.迭代逼近(poj3301)隨機化演算法(poj3318,poj2454)雜題(poj1870,poj3296,poj3286,poj1095)

七.計算幾何學.

座標離散化.掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用) (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)多邊形的核心(半平面交)(poj3130,poj3335)幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高階（regional中等難度）:一.基本演算法要求:

程式碼快速寫成,精簡但不失風格(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446最優比率生成樹. (poj2728)最小樹形圖(poj3164)次小生成樹.無向圖、有向圖的最小環

三.資料結構.

trie圖的建立和應用. (poj2778)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 線上演算法(RMQ+dfs)).(poj1330)雙端佇列和它的應用(維護一個單調的佇列,常常在動態規劃中起到最佳化狀態轉移的目的). (poj2823)左偏樹(可合併堆).字尾樹(非常有用的資料結構,也是賽區考題的熱點).(poj3415,poj3294)

四.搜尋

較麻煩的搜尋題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)廣搜的狀態最佳化:利用M進位制數儲存狀態、轉化為串用hash表判重、按位壓縮儲存狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)深搜的最佳化:儘量用位運算、一定要加剪枝、函式引數儘可能少、層數不易過大、可以考慮雙向搜尋或者是輪換搜尋、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用資料結構最佳化的動態規劃.(poj2754,poj3378,poj3017)四邊形不等式理論.較難的狀態DP(poj3133)

六.數學

組合數學. 1.MoBius反演(poj2888,poj2154) 2.偏序關係理論.博奕論. 1.極大極小過程(poj3317,poj1085) 2.Nim問題.

七.計算幾何學.

半平面求交(poj3384,poj2540)可檢視的建立(poj2966)點集最小圓覆蓋.對踵點(poj2079)

八.綜合題. (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

更多內容參考資料：https://www.zhihu.com/question/23148377

根據我的經驗，最好演算法課本上的都知道一下幹啥用的。但絕大部分不需要深入。因為一般來說你90%用不上。而用上的時候90%應該該去找現成測試透過的。

比如說，排序演算法，JAVA裡面預設的是歸併，並且當足夠短的時候是冒泡。雜湊演算法裡面當雜湊值一樣的時候，夠短用連結串列，長了紅黑樹。

你會發現實際往往是多重場景，而通常你要做的只是選擇更合適的，根本不需要自己寫。只有非常罕見的場景，才要自己寫一個。

這種情況下，演算法沒有說那種必須掌握，而是知道的多更好一些。需要知道各自優缺點，應用場景。另外，如果不是專門的演算法工程師，設計模式去學一下可能也不錯。

演算法一：快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個專案要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。

演算法步驟：

1 從數列中挑出一個元素，稱為 “基準”（pivot），

2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割槽退出之後，該基準就處於數列的中間位置。這個稱為分割槽（partition）操作。

3 遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

演算法二：堆排序演算法

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆排序的平均時間複雜度為Ο(nlogn) 。

演算法步驟：

建立一個堆H[0..n-1]

把堆首（最大值）和堆尾互換

3. 把堆的尺寸縮小1，並呼叫shift_down(0),目的是把新的陣列頂端資料調整到相應位置

4. 重複步驟2，直到堆的尺寸為1

演算法三：歸併排序

歸併排序（Merge sort，臺灣譯作：合併排序）是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

演算法步驟：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列

2. 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置

3. 比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置

4. 重複步驟3直到某一指標達到序列尾

5. 將另一序列剩下的所有元素直接複製到合併序列尾

演算法四：二分查詢演算法

二分查詢演算法是一種在有序陣列中查詢某一特定元素的搜尋演算法。搜素過程從陣列的中間元素開始，如果中間元素正好是要查詢的元素，則搜 素過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中查詢，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列 為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。折半搜尋每次把搜尋區域減少一半，時間複雜度為Ο(logn) 。

演算法五：BFPRT(線性查詢演算法)

BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，透過巧妙的分 析，BFPRT可以保證在最壞情況下仍為線性時間複雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間複雜 度，五位演算法作者做了精妙的處理。

演算法步驟：

1. 將n個元素每5個一組，分成n/5(上界)組。

2. 取出每一組的中位數，任意排序方法，比如插入排序。

3. 遞迴的呼叫selection演算法查詢上一步中所有中位數的中位數，設為x，偶數箇中位數的情況下設定為選取中間小的一個。

4. 用x來分割陣列，設小於等於x的個數為k，大於x的個數即為n-k。

5. 若i==k，返回x；若i<k，在小於x的元素中遞迴查詢第i小的元素；若i>k，在大於x的元素中遞迴查詢第i-k小的元素。

終止條件：n=1時，返回的即是i小元素。

演算法六：DFS（深度優先搜尋）

深度優先搜尋演算法（Depth-First-Search），是搜尋演算法的一種。它沿著樹的深度遍歷樹的節點，儘可能深的搜尋樹的分 支。當節點v的所有邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被髮 現的節點，則選擇其中一個作為源節點並重復以上過程，整個程序反覆進行直到所有節點都被訪問為止。DFS屬於盲目搜尋。

深度優先搜尋是圖論中的經典演算法，利用深度優先搜尋演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆資料結構來輔助實現DFS演算法。

深度優先遍歷圖演算法步驟：

1. 訪問頂點v；

2. 依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；

3. 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。

上述描述可能比較抽象，舉個例項：

DFS 在訪問圖中某一起始頂點 v 後，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然後再從 w2 出發，進行類似的訪問，… 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜尋。重複上述過程，直到連通圖中所有頂點都被訪問過為止。

演算法七：BFS(廣度優先搜尋)

廣度優先搜尋演算法（Breadth-First-Search），是一種圖形搜尋演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。BFS同樣屬於盲目搜尋。一般用佇列資料結構來輔助實現BFS演算法。

演算法步驟：

1. 首先將根節點放入佇列中。

2. 從佇列中取出第一個節點，並檢驗它是否為目標。

如果找到目標，則結束搜尋並回傳結果。

否則將它所有尚未檢驗過的直接子節點加入佇列中。

3. 若佇列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳“找不到目標”。

4. 重複步驟2。

演算法八：Dijkstra演算法

戴克斯特拉演算法（Dijkstra’s algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜尋解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模組。

該演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函式 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。

演算法步驟：

1. 初始時令 S={V0},T={其餘頂點}，T中頂點對應的距離值

若存在<v0,vi>，d(V0,Vi)為<v0,vi>弧上的權值

若不存在<v0,vi>，d(V0,Vi)為∞

2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值

重複上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

演算法九：動態規劃演算法

動態規劃（Dynamic programming）是一種在數學、計算機科學和經濟學中使用的，透過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合併子問題的解以得出原問題的解。 通常許多 子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化儲存，以便下次需要同一個 子問題解之時直接查表。 這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。

關於動態規劃最經典的問題當屬揹包問題。

演算法步驟：

1. 最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最最佳化原理）。最優子結構性質為動態規劃演算法解決問題提供了重要線索。

2. 子問題重疊性質。子問題重疊性質是指在用遞迴演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。 動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是 在表格中簡單地檢視一下結果，從而獲得較高的效率。

演算法十：樸素貝葉斯分類演算法

樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單機率分類演算法。貝葉斯分類的基礎是機率推理，就是在各種條件的存在不確定，僅知其出現機率的情況下， 如何完成推理和決策任務。機率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。

樸素貝葉斯分類器依靠精確的自然機率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型引數估計使用最大似然估計方法，換言之樸素貝葉斯模型能工作並沒有用到貝葉斯機率或者任何貝葉斯模型。

一、演算法最最基礎

1、時間複雜度

2、空間複雜度

一般最先接觸的就是時間複雜度和空間複雜度的學習了，這兩個概念以及如何計算，是必須學的，也是必須最先學的，主要有最大複雜度、平均複雜度等，直接透過部落格搜尋學習即可。

二、基礎資料結構

1、線性表

列表（必學）

連結串列（必學）

跳躍表（知道原理，應用，最後自己實現一遍）

並查集（建議結合刷題學習）

不用說，連結串列、列表必須，不過重點是連結串列。

2、棧與佇列

棧（必學）

佇列（必學）

優先佇列、堆（必學）

多級反饋佇列（原理與應用）

特別是優先佇列，再刷題的時候，還是經常用到的，佇列與棧，是最基本的資料結構，必學。可以透過部落格來學習。

3、雜湊表（必學）

碰撞解決方法：開放定址法、鏈地址法、再次雜湊法、建立公共溢位區（必學）

布隆過濾器

4、樹

二叉樹：各種遍歷（遞迴與非遞迴）（必學）

哈夫曼樹與編碼（原理與應用）

AVL樹（必學）

B 樹與 B+ 樹（原理與應用）

字首樹（原理與應用）

紅黑樹（原理與應用）

線段樹（原理與應用）

5、陣列

樹狀陣列

矩陣（必學）

樹狀陣列其實我也沒學過，，，，

三、各種常見演算法

1、十大排序演算法

簡單排序：插入排序、選擇排序、氣泡排序（必學）

分治排序：快速排序、歸併排序（必學，快速排序還要關注中軸的選取方式）

分配排序：桶排序、基數排序

樹狀排序：堆排序（必學）

其他：計數排序（必學）、希爾排序

對於十大演算法的學習，假如你不大懂的話，那麼我還是挺推薦你去看書的，因為看了書，你可能不僅僅知道這個演算法怎麼寫，還能知道他是怎麼來的。推薦書籍是《演算法第四版》，這本書講的很詳細，而且配了很多圖演示，還是挺好懂的。

2、圖論演算法

圖的表示：鄰接矩陣和鄰接表

遍歷演算法：深度搜索和廣度搜索(必學)

最短路徑演算法：Floyd，Dijkstra（必學）

最小生成樹演算法：Prim，Kruskal（必學）

實際常用演算法：關鍵路徑、拓撲排序（原理與應用）

二分圖匹配：配對、匈牙利演算法（原理與應用）

拓展：中心性演算法、社群發現演算法（原理與應用）

圖還是比較難的，不過我覺得圖涉及到的挺多演算法都是挺實用的，例如最短路徑的計算等，圖相關的，我這裡還是建議看書的，可以看《演算法第四版》。

漫畫：什麼是 “圖”？（修訂版）

漫畫：深度優先遍歷 和 廣度優先遍歷

漫畫：圖的 “最短路徑” 問題

漫畫：Dijkstra 演算法的最佳化

漫畫：圖的 “多源” 最短路徑

3、搜尋與回溯演算法

貪心演算法（必學）

啟發式搜尋演算法：A*尋路演算法（瞭解）

地圖著色演算法、N 皇后問題、最優加工順序

旅行商問題

這方便的只是都是一些演算法相關的，我覺得如果可以，都學一下。像貪心演算法的思想，就必須學的了。建議透過刷題來學習，leetcode 直接專題刷。

4、動態規劃

樹形DP：01揹包問題

線性DP：最長公共子序列、最長公共子串

區間DP：矩陣最大值（和以及積）

數位DP：數字遊戲

狀態壓縮DP：旅行商

我覺得動態規劃是最難的一個演算法思想了，記得當初第一次接觸動態規劃的時候，是看01揹包問題的，看了好久都不大懂，懵懵懂懂，後面懂了基本思想，可是做題下不了手，但是看的懂答案。一氣之下，再leetcdoe專題連續刷了幾十道，才掌握了動態規劃的套路，也有了自己的一套模板。不過說實話，動態規劃，是考的真他媽多，學習演算法、刷題，一定要掌握。這裡建議先了解動態規劃是什麼，之後 leetcode 專題刷，反正就一般上面這幾種題型。後面有時間，我也寫一下我學到的套路，有點類似於我之前寫的遞迴那樣，算是一種經驗。也就是我做題時的模板，不過感覺得寫七八個小時，，，，，有時間就寫。之前寫的遞迴文章：為什麼你學不會遞迴？告別遞迴，談談我的一些經驗

5、字元匹配演算法

正則表示式

模式匹配：KMP、Boyer-Moore

我寫過兩篇字串匹配的文章，感覺還不錯，看了這兩篇文章，我覺得你就差不多懂 kmp 和 Boyer-Moore 了。

字串匹配Boyer-Moore演算法：文字編輯器中的查詢功能是如何實現的？

6、流相關演算法

最大流：最短增廣路、Dinic 演算法

最大流最小割：最大收益問題、方格取數問題

最小費用最大流：最小費用路、消遣

這方面的一些演算法，我也只瞭解過一些，感興趣的可以學習下。

這要看，你想做哪個方面的程式設計師。

程式設計師有後端、前端、移動端、大資料、AI等。如果只是純前端和移動端而言，演算法掌握基礎的排序、紅黑樹、雜湊等也就差不多了，更加高深的也用不到，更多的是系統API就提供了很多演算法方法。總不見得，寫的能比系統的好吧。如果只是想作為一個普通的程式設計師，不想著往高階和架構方向走，那麼不接觸演算法，你會發現也行，活照做。但是呢，水往高處流，演算法還是需要的。尤其像大資料和人工智慧，演算法是必須會的，而演算法而言，就是數學。

人工智慧來說，線性代數、機率論等是一個很重要的，不單是演算法可以來解釋。還有資訊理論，計算資訊傳遞熵。個人推薦，可以看下國外的程式設計大賽，裡面有很多考驗演算法的，平時開發中，多思考怎樣減少資訊傳遞，提高程式碼效率，這也是演算法的一種。

必須瞭解，掌握的：1.樹，2.雜湊，3.正則，4.圖演算法，5.串匹配，6.運輸流

但是更多的是掌握那些經典的數學計算演算法，這才是根本。演算法脫離不了數學，演算法玩的好的，一般數學都好。推薦平時，多去看看《線性代數》《高等數學》還有偏向計算機的演算法書籍，會有所幫助。再去看看國外程式設計大賽的題目，別人寫的程式，從中會對演算法有更大的啟發。但作為程式設計師，演算法只是一部分，更重要的是怎樣快速迭代，減少開發成本，怎樣貼合業務等。

優秀程式設計師該學的32個演算法！！

1、A搜尋演算法——圖形搜尋演算法，作為啟發式搜尋演算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低透過成本的演算法，常用於遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。

從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算透過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜尋演算法是最佳優先搜尋的範例。

2、集束搜尋（又名定向搜尋，Beam Search）——最佳優先搜尋演算法的最佳化。使用啟發式函式評估它檢查的每個節點的能力。不過，集束搜尋只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

通常用在圖的解空間比較大的情況下，為了減少搜尋所佔用的空間和時間，在每一步深度擴充套件的時候，剪掉一些質量比較差的結點，保留下一些質量較高的結點。這樣減少了空間消耗，並提高了時間效率

演算法的工作流程如下：

使用廣度優先策略建立搜尋樹，在樹的每一層，按照啟發代價對節點進行排序，然後僅留下預先確定的個數（Beam Width-集束寬度）的節點，僅這些節點在下一層次繼續擴充套件，其他節點就被剪掉了。

將初始節點插入到list中，

將給節點出堆，如果該節點是目標節點，則演算法結束；

否則擴充套件該節點，取集束寬度的節點入堆。然後到第二步繼續迴圈。

演算法結束的條件是找到最優解或者堆為空。

3、二分查詢（Binary Search）——線上性陣列中找特定值的演算法，每個步驟去掉一半不符合要求的資料。

二分查詢的基本思想是：

設R[low..high]是當前的查詢區間

（1）首先確定該區間的中點位置：

（2）然後將待查的K值與R[mid].key比較：若相等，則查詢成功並返回此位置，否則須確定新的查詢區間，繼續二分查詢，具體方法如下：

① 若R[mid].key>K，則由表的有序性可知R[mid..n].keys均大於K，因此若表中存在關鍵字等於K的結點，則該結點必定是在位置mid左邊的子表R[1..mid-1]中，故新的查詢區間是左子表R[1..mid-1]。

② 若R[mid].key<K，則要查詢的K必在mid的右子表R[mid+1..n]中，即新的查詢區間是右子表R[mid+1..n]。下一次查詢是針對新的查詢區間進行的。

4、分支界定演算法（Branch and Bound）——在多種最最佳化問題中尋找特定最最佳化解決方案的演算法，特別是針對離散、組合的最最佳化。

搜尋策略是：

B在產生的孩子節點中，剪掉那些不可能產生可行解（或最優解）的節點；（使用限定條件）

C將其餘所有的孩子節點加入活節點連結串列；

D從活結點表中選擇下一個活結點作為新的擴充套件節點；

E遇到層結束標記（採取不同的資料結構實現可能不同， 加入新的結束標記）

如此迴圈，直到找到問題的可行解（或最優解）或者活結點表為空。

分支界定法的思想是：首先確定目標值的上下界， 邊搜尋邊減掉搜尋樹的某些枝， 提高搜尋效率。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

7、Diffie-Hellman金鑰交換演算法——一種加密協議，允許雙方在事先不瞭解對方的情況下，在不安全的通訊通道中，共同建立共享金鑰。該金鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法（Discrete differentiation）

10、動態規劃演算法（Dynamic Programming）——展示互相覆蓋的子問題和最優子架構演算法

11、歐幾里得演算法（Euclidean algorithm）——計算兩個整數的最大公約數。最古老的演算法之一，出現在公元前300前歐幾里得的《幾何原本》。

12、期望-最大演算法（Expectation-maximization algorithm，又名EM-Training）——在統計計算中，期望-最大演算法在機率模型中尋找可能性最大的引數估算值，其中模型依賴於未發現的潛在變數。EM在兩個步驟中交替計算，第一步是計算期望，利用對隱藏變數的現有估計值，計算其最大可能估計值；第二步是最大化，最大化在第一步上求得的最大可能值來計算引數的值。

13、快速傅立葉變換（Fast Fourier transform，FFT）——計算離散的傅立葉變換（DFT）及其反轉。該演算法應用範圍很廣，從數字訊號處理到解決偏微分方程，到快速計算大整數乘積。

14、梯度下降（Gradient descent）——一種數學上的最最佳化演算法。

15、雜湊演算法（Hashing）

Hash演算法是一種只能加密不能解密的演算法，可以將任意長度的資訊轉成雜亂的固定長度的字串，叫做Hash值，又稱“訊息摘要”（Message Digest)也可以說，hash就是找到一種資料內容和資料存放地址之間的對映關係。由於非對稱演算法的運算速度較慢，所以在數字簽名協議中，雜湊函式扮演了一個重要的角色而被用於數字簽名。

雜湊演算法具有以下2個特點：

1.輸入值只要改變一點，輸出的hash值會天差地別。因此只有完全一樣的輸入值才能達到完全一樣的輸出值2.輸入值和輸出值之間沒有規律，所以不能透過輸出值反推出輸入值。

16、堆排序（Heaps）

指利用堆積樹（堆）這種資料結構所設計的一種排序演算法，它是選擇排序的一種。可以利用陣列的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。

17、Karatsuba乘法——需要完成上千位整數的乘法的系統中使用，比如計算機代數系統和大數程式庫，如果使用長乘法，速度太慢。該演算法發現於1962年。

18、LLL演算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格規約（lattice）基數為輸入，輸出短正交向量基數。LLL演算法在以下公共金鑰加密方法中有大量使用：揹包加密系統（knapsack）、有特定設定的RSA加密等等。

19、最大流量演算法（Maximum flow）——該演算法試圖從一個流量網路中找到最大的流。它優勢被定義為找到這樣一個流的值。最大流問題可以看作更復雜的網路流問題的特定情況。最大流與網路中的介面有關，這就是最大流-最小截定理（Max-flow min-cut theorem）。Ford-Fulkerson 能找到一個流網路中的最大流。

20、合併排序（Merge Sort）

具體步驟如下：

將待排序的陣列分成左右兩部分。再將這兩部分分別分成左右兩部分。一直分下去，直到不可分（每部分只有一個元素）。由於陣列被分成許多的單個數據，比較起來就簡單了，然後開始合併，合併的同時排序。持續合併直到得到排好序的陣列。

下面這幅圖可以幫助你理解演算法過程：

21、牛頓法（Newton"s method）——求非線性方程（組）零點的一種重要的迭代法。

同梯度下降法一樣，是一種最佳化演算法，其應用如可解決logistic迴歸於分類問題中的似然函式最大化。

其是一種用於求函式零點的數值方法。

22、Q-learning學習演算法——這是一種透過學習動作值函式（action-value function）完成的強化學習演算法，函式採取在給定狀態的給定動作，並計算出期望的效用價值，在此後遵循固定的策略。Q-leanring的優勢是，在不需要環境模型的情況下，可以對比可採納行動的期望效用。

23、兩次篩法（Quadratic Sieve）——現代整數因子分解演算法，在實踐中，是目前已知第二快的此類演算法（僅次於數域篩法Number Field Sieve）。對於110位以下的十位整數，它仍是最快的，而且都認為它比數域篩法更簡單。

24、RANSAC——是“RANdom SAmple Consensus”的縮寫。該演算法根據一系列觀察得到的資料，資料中包含異常值，估算一個數學模型的引數值。其基本假設是：資料包含非異化值，也就是能夠透過某些模型引數解釋的值，異化值就是那些不符合模型的資料點。

25、RSA——公鑰加密演算法。首個適用於以簽名作為加密的演算法。RSA在電商行業中仍大規模使用，大家也相信它有足夠安全長度的公鑰。

26、Schönhage-Strassen演算法——在數學中，Schönhage-Strassen演算法是用來完成大整數的乘法的快速漸近演算法。其演算法複雜度為：O(N log(N) log(log(N)))，該演算法使用了傅立葉變換。

27、單純型演算法（Simplex Algorithm）——在數學的最佳化理論中，單純型演算法是常用的技術，用來找到線性規劃問題的數值解。線性規劃問題包括在一組實變數上的一系列線性不等式組，以及一個等待最大化（或最小化）的固定線性函式。

28、奇異值分解（Singular value decomposition，簡稱SVD）——線上性代數中，SVD是重要的實數或複數矩陣的分解方法，在訊號處理和統計中有多種應用，比如計算矩陣的偽逆矩陣（以求解最小二乘法問題）、解決超定線性系統（overdetermined linear systems）、矩陣逼近、數值天氣預報等等。

29、求解線性方程組（Solving a system of linear equations）——線性方程組是數學中最古老的問題，它們有很多應用，比如在數字訊號處理、線性規劃中的估算和預測、數值分析中的非線性問題逼近等等。求解線性方程組，可以使用高斯—約當消去法（Gauss-Jordan elimination），或是柯列斯基分解（ Cholesky decomposition）。

Strukturtensor演算法——應用於模式識別領域，為所有畫素找出一種計算方法，看看該畫素是否處於同質區域（ homogenous region），看看它是否屬於邊緣，還是是一個頂點。

30、合併查詢演算法（Union-find）——給定一組元素，該演算法常常用來把這些元素分為多個分離的、彼此不重合的組。不相交集（disjoint-set）的資料結構可以跟蹤這樣的切分方法。合併查詢演算法可以在此種資料結構上完成兩個有用的操作：

I、查詢：判斷某特定元素屬於哪個組。

II、合併：聯合或合併兩個組為一個組。

31、維特比演算法（Viterbi algorithm）——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

32、維特比演算法（Viterbi algorithm）——尋找隱藏狀態最有可能序列的動態規劃演算法，這種序列被稱為維特比路徑，其結果是一系列可以觀察到的事件，特別是在隱藏的Markov模型中。

使用紅黑樹來解決Hash碰撞衝突的問題；

計算sizeStamp的時候，呼叫了Interger中的方法，使用位運算來求出給定數leading zero的數量，當然使用sizeStamp這種方式也算是另闢蹊徑吧；

presize中，使用位運算來求出不小於一個數的最小的2的冪；

transfer中，table[i]指向的連結串列或紅黑樹中的所有節點，根據hash&n是否為0分別放在table[i]和table[i+n]中，之所以可以這樣劃分，是因為table陣列的長度n是2的冪，這種數字關係挺微妙。

DelayQueue

take中，使用leader/follower模式，避免執行緒切換的開銷，從而達到減少等待時間的目的。

PriorityBlockingQueue

使用陣列維護了一個最小堆。

樓上寫的太多了，一般程式設計師都不會掌握的，把有限的時間花費到重要的演算法上。

1.快速排序演算法

2.歸併排序演算法

3.堆排序演算法

4.二分查詢演算法

5.BFPRT線性查詢演算法

6.DFS深度優先搜尋

7.BFS廣度優先演算法

8.動態規劃

9.樸素貝葉斯分類

希望以幫助哈！

起碼一些教材式經典演算法要知道，包括排序演算法，圖演算法，串匹配演算法，運輸流演算法，還有一些經典的數學計算演算法，比如大規模矩陣乘法，傅立葉積分演算法。等等有很多，雖然不一定都用的到，但這些耳熟能詳的經典演算法必須有所瞭解。等到工作後會接觸到相關的專業演算法，再加以學習