對C/C++初學者來說，很多入門級的演算法是學習和筆試的基礎，可否列出你所知道或筆試遇到的那些有意思的演算法？

01-16

對於這些必須掌握的基礎演算法，不同的學習階段有不同的感受，或許大牛們都覺得簡單，但很多經常在考試和面試中出現，所以想利用知乎的影響力和本著有益於後來初學者與面試者的考慮，請各位把你在學習和工作面試中遇到的那些小演算法列出來，不求具體解法，只求你第一印象深，覺得入門者必須知道的那些演算法，寫出自己心目中的列表。
說明：1.真的感謝各位大大的批評，文字表達不好，對不住了。
2.我補充一下提出這個問題的原因：
1）HR反應了一些筆試結果，很多筆試者抱怨題目簡單沒含金量，很多答案網上書上就有，無法測試一個程序員真實水平。那我想問問各位大大，你們遇到的筆試編程題都是什麼樣子的，筆試編程題要複雜到什麼程度。
2）我看了一些收上來的答案，真心表示，能做出來的並沒有想像的多，大概40%不到。那麼問題來了，是什麼原因導致了這種情況出現？很多人給出了大致代碼，但細究很多細節有問題。所以是否如題，有必要做個總結，把各位面試筆試遇到的，或是自己作為面試官出過的小編程題分享出來，讓後來者知道哪些是基礎的演算法，必須要紮實掌握的。

3）答案中很多人給出了演算法導論，編程珠璣，這些提問者都看過或是曾經面試前刷過，但自己從沒有總結過。原因只是「自己會了，考試過了，就可以了」。但後來幫HR做面試，包括社招和校招，發現有些人的能力還是不錯的，但是考查基礎演算法時，發現很多這些小演算法裡面還是有很多值得注意的小技巧，很多人如果想不到，可能在面試過程中一下子做不出來。這也算是幫面試者列出一個表單，以供大家查缺補漏。。。

說了10000000000遍了演算法導論，你自己不去找

我倒是覺得你如果認為沒有，那麼學習完了以後自己能總結歸納出這一套東西的話，進步會很大。不要啥東西都想靠別人送到你嘴裡，總有一天得靠自己的。

「從來沒有人能對此做過」，這是一個病句。

原文: Matrix67：參加省選和NOI還需要哪些知識？

時間複雜度（漸近時間複雜度的嚴格定義，NP問題，時間複雜度的分析方法，主定理）

排序演算法（平方排序演算法的應用，Shell排序，快速排序，歸併排序，時間複雜度下界，三種線性時間排序，外部排序）

數論（整除，集合論，關係，素數，進位制，輾轉相除，擴展的輾轉相除，同餘運算，解線性同餘方程，中國剩餘定理）

指針（鏈表，搜索判重，鄰接表，開散列，二叉樹的表示，多叉樹的表示）

按位運算（and，or，xor，shl，shr，一些應用）

圖論（圖論模型的建立，平面圖，歐拉公式與五色定理，求強連通分量，求割點和橋，歐拉迴路，AOV問題，AOE問題，最小生成樹的三種演算法，最短路的三種演算法，標號法，差分約束系統，驗證二分圖，Konig定理，匈牙利演算法，KM演算法，穩定婚姻系統，最大流演算法，最小割最大流定理，最小費用最大流演算法）

計算幾何（平面解幾及其應用，向量，點積及其應用，叉積及其應用，半平面相交，求點集的凸包，最近點對問題，凸多邊形的交，離散化與掃描）

數據結構（廣度優先搜索，驗證括弧匹配，表達式計算，遞歸的編譯，Hash表，分段Hash，並查集，Tarjan演算法，二叉堆，左偏樹，斜堆，二項堆，二叉查找樹，AVL，Treap，Splay，靜態二叉查找樹，2-d樹，線段樹，二維線段樹，矩形樹，Trie樹，塊狀鏈表）

組合數學（排列與組合，鴿籠原理，容斥原理，遞推，Fibonacci數列，Catalan數列，Stirling數，差分序列，生成函數，置換，Polya原理）

概率論（簡單概率，條件概率，Bayes定理，期望值）

矩陣（矩陣的概念和運算，二分求解線性遞推方程，多米諾骨牌棋盤覆蓋方案數，高斯消元）

字元串處理（KMP，後綴樹，有限狀態自動機，Huffman編碼，簡單密碼學）

動態規劃（單調隊列，凸完全單調性，樹型動規，多叉轉二叉，狀態壓縮類動規，四邊形不等式）

博奕論（Nim取子遊戲，博弈樹，Shannon開關遊戲）

搜索（A*，ID，IDA*，隨機調整，遺傳演算法）

微積分初步（極限思想，導數，積分，定積分，立體解析幾何）

---------------------------

再補充一點

樹鏈剖分樹dfs序列分塊搞法

乘法逆元高斯消元牛頓迭代

雙連通分量動態樹線性規劃轉網路流

樹分治三維凸包旋轉卡殼

《大話數據結構》

《演算法（第四版）》

裡面的基本夠用了。而且都有源代碼，去刷吧。

做不出來是我們普通人跟大牛思維能力上的差距造成的，短時間沒辦法。

學完基本的數據結構是做不出的，裡面很多技巧是思維的體現，不是知識的體現。

推薦一些書，看了然後記住

《劍指offer》

《編程之美》

《編程珠璣》

《程序員面試金典》

《leetcode題解》

然後你可以用各大公司題目練手

另外要把編程語言搞熟，不要栽在語言題上

操作系統，網路，資料庫也不要落下

隨便找本演算法/數據結構的書籍，翻開目錄。再回過頭來看看你的問題還是問題嗎

演算法導論到現在為止還在書架上沒有勇氣翻開，題主可以去coursera搜有Algorithms part1 共八周課程，應該是最基礎的了推薦給你

我先列一個出來：

************************************遞歸演算法類*******************************************

1.漢諾塔

2.8皇后

3.N階乘

4.最大子序列和

5.最大公因數

6.二分搜索

7.背包問題

8.冪乘演算法

（請列出來的演算法，要有普遍性不要太複雜，比如以上演算法大多不超過50行）