在編程和演算法領域，有哪些經典問題？

01-05

fibonacci 是一個, 我先說掉了...

剛剛才看到一篇百度百科經典演算法合集，貼到著來。共勉啊親~！

排序

排序演算法:http://baike.baidu.com/view/297739.htm

冒泡排序法:http://baike.baidu.com/view/1313793.htm

起泡法:http://baike.baidu.com/view/174304.htm

雞尾酒排序:http://baike.baidu.com/view/1981861.htm

桶排序:http://baike.baidu.com/view/1784217.htm

計數排序:http://baike.baidu.com/view/1209480.htm

歸併排序:http://baike.baidu.com/view/90797.htm

排序二叉樹:http://baike.baidu.com/view/922220.html

鴿巢排序:http://baike.baidu.com/view/2020276.htm

基數排序:http://baike.baidu.com/view/1170573.htm

選擇排序法:http://baike.baidu.com/view/1575807.htm

希爾排序:http://baike.baidu.com/view/178698.htm

堆排序:http://baike.baidu.com/view/157305.htm

快速排序演算法:http://baike.baidu.com/view/19016.htm

插入排序法:http://baike.baidu.com/view/1443814.htm

樹形選擇排序:http://baike.baidu.com/view/3108940.html

========================================================

搜索

深度優先搜索:http://baike.baidu.com/view/288277.htm

寬度優先搜索:http://baike.baidu.com/view/825760.htm

啟發式搜索:http://baike.baidu.com/view/1237243.htm

蟻群演算法:http://baike.baidu.com/view/539346.htm

遺傳演算法:http://baike.baidu.com/view/45853.htm

========================================================

計算幾何

凸包:http://baike.baidu.com/view/707209.html

========================================================

圖論

哈夫曼編碼:http://baike.baidu.com/view/95311.htm

二叉樹遍歷:http://baike.baidu.com/view/549587.html

最短路徑:http://baike.baidu.com/view/349189.htm

Dijkstra演算法:http://baike.baidu.com/view/7839.htm

A*演算法:http://baike.baidu.com/view/7850.htm

SPFA演算法:http://baike.baidu.com/view/682464.html

Bellman-Ford演算法:http://baike.baidu.com/view/1481053.htm

floyd-warshall演算法:http://baike.baidu.com/view/2749461.htm

Dijkstra演算法:http://baike.baidu.com/view/7839.htm

最小生成樹:http://baike.baidu.com/view/288214.htm

Prim演算法:http://baike.baidu.com/view/671819.html

網路流:http://baike.baidu.com/view/165435.html

========================================================

動態規劃

動態規劃:http://baike.baidu.com/view/28146.htm

哈密頓圖:http://baike.baidu.com/view/143350.html

遞推:http://baike.baidu.com/view/3783120.htm

========================================================

動態規劃優化

優先隊列:http://baike.baidu.com/view/1267829.htm

單調隊列:http://baike.baidu.com/view/3771451.htm

四邊形不等式:http://baike.baidu.com/view/1985058.htm

========================================================

其他

隨機化演算法:http://baike.baidu.com/view/1071553.htm

遞歸:http://baike.baidu.com/view/96473.htm

窮舉搜索法:http://baike.baidu.com/view/1189634.htm

貪心演算法:http://baike.baidu.com/view/112297.htm

分治法:http://baike.baidu.com/view/1583824.htm

迭代法:http://baike.baidu.com/view/649495.htm

加密演算法:http://baike.baidu.com/view/155969.htm

回溯法:http://baike.baidu.com/view/45.htm

弦截法:http://baike.baidu.com/view/768310.htm

迭代法:http://baike.baidu.com/view/649495.htm

背包問題:http://baike.baidu.com/view/841810.htm

http://baike.baidu.com/view/1731915.htm

八皇后問題:http://baike.baidu.com/view/698719.htm

百雞問題:http://baike.baidu.com/view/367996.htm

二分法:http://baike.baidu.com/view/75441.htm

kmp演算法:http://baike.baidu.com/view/659777.html

遺傳演算法:http://baike.baidu.com/view/45853.htm

矩陣乘法:http://www.douban.com/group/topic/12416781/edit

Floyd演算法:http://baike.baidu.com/view/14495.html

路由演算法:http://baike.baidu.com/view/2276401.html

ICP演算法:http://baike.baidu.com/view/1954001.html

約瑟夫環:http://baike.baidu.com/view/717633.htm

約瑟夫問題:http://baike.baidu.com/view/213217.htm

AVL樹:http://baike.baidu.com/view/414610.htm

紅黑樹:http://baike.baidu.com/view/133754.htm

退火演算法:http://baike.baidu.com/view/335371.htm#sub335371

並查集:http://baike.baidu.com/view/521705.htm

線段樹:http://baike.baidu.com/view/670683.htm

左偏樹:http://baike.baidu.com/view/2918906.htm

Treap:http://baike.baidu.com/view/956602.htm

Trie樹:http://baike.baidu.com/view/1436495.html

RMQ:http://baike.baidu.com/view/1536346.htm

LCA :http://baike.baidu.com/view/409050.htm

矩陣乘法:http://baike.baidu.com/view/2455255.htm

高斯消元:http://baike.baidu.com/view/33268.html

銀行家演算法:http://baike.baidu.com/view/93075.htm

*分類參照維基百科裡演算法的分類http://zh.wikipedia.org/zh-cn/%E7%AE%97%E6%B3%95

經典演算法：

遞歸：漢諾塔，全排列的生成等

分治法：快速排序、歸併排序等

貪心法：背包問題、Dijkstra、Prim演算法

動態規劃：0-1背包問題，各種子串問題

搜索法：N皇后問題、迷宮問題

隨機演算法：蒙特卡洛、隨機快排等

近似演算法：TSP等方面相關演算法等

在線演算法：K-伺服器問題等

應用方面的演算法：

K-Means、ID3等演算法

以上都是經典的不能再經典的演算法，也是演算法入門必讀

從程序員面試角度來說，經典的問題包括以下內容：

演算法部分

二分搜索 Binary Search 分治 Divide Conquer 寬度優先搜索 Breadth First Search 深度優先搜索 Depth First Search 回溯法 Backtracking 雙指針 Two Pointers 動態規劃 Dynamic Programming 掃描線 Scan-line algorithm 快排 Quick Sort

數據結構部分

棧 Stack 隊列 Queue 鏈表 Linked List 數組 Array 哈希表 Hash Table 二叉樹 Binary Tree 堆 Heap 並查集 Union Find 字典樹 Trie

我搜集了最近的Google面試題，你可以大致感受一下在大公司面試中會出現的一些面試演算法題：

· Google 面試題 | 分餅乾

· Google 面試題 | 重複子字元串模式

· Google 面試題 | 最優賬戶結餘

· Google 面試題 | 132 模式

· Google 面試題 | 檢查子序列

· Google 面試題 | 目標和

· Google 面試題 | 建郵局

· Google 面試題 | 0與1的問題

· Google 面試題 | 驗證UTF-8

· Google 面試題 | 二進位手錶

· Google 面試題 | 硬幣排成一條線3

· Google 面試題 | 除法求值

· Google 面試題 | 不同的子序列解法1

· Google 面試題 | 貪吃蛇

· Google 面試題 | 數字計數

· Google 面試題 | Palindrome Partitioning II

· Google 面試題 | 最大可分子集

· Google 面試題 | 軸對稱

· Google 面試題 | 俄羅斯套娃信封

· Google 面試題 | Search a 2D Matrix II

· Google 面試題 | 尋找中位數

· Google 面試題 | 路線重現

· Google 面試題 | Data Stream Median - Python版

· Google 面試題 | 數組補丁

· Google 面試題 | 不構造樹的情況下驗證先序遍歷

· Google 面試題 | 擺動排序 II

· Google 面試題 | 矩陣中的最長上升路徑

· Google 面試題 | 島嶼計數2

· Google 面試題 | Count of Smaller Numbers After Self(數組計數)

· Google 面試題 | 翻轉遊戲（Flip Game II)

· Google 面試題 | 吹氣球

· Google 面試題 | 去除文件中的重複行

· Google 面試題 | 最多有k個不同字元的最長子字元串

歡迎關注我的微信公眾號：九章演算法（ninechapter），幫助你獲得面試、拿到offer、找到好工作！

我覺得終極問題應該是，寫一個程序，掃描一個exe文件，然後判斷是否跟產品狗給出的docx一致（逃

石子歸併問題。n堆石子擺成一條線。現要將石子有次序地合併成一堆。規定每次只能選相鄰的2堆石子合併成新的一堆，並將新的一堆石子數記為該次合併的代價。試設計一個演算法，計算出將n堆石子合併成一堆的最小代價。

舉個例子，比如： 1 2 3 4，有不少合併方法，比如

1 2 3 4 =&> 3 3 4(3) =&> 6 4(9) =&> 10(19)

1 2 3 4 =&> 1 5 4(5) =&> 1 9(14) =&> 10(24)

1 2 3 4 =&> 1 2 7(7) =&> 3 7(10) =&> 10(20)

括弧裡面為總代價，可以看出，第一種方法的代價最低，現在隨便給出n堆石子，用程序算出這個最小合併代價。

買本算導配著編程之美看看吧。

背包，八皇后，九數碼

拖了好久～拖延症要不得啊～～～

前面有各位大神全面介紹了很多經典演算法。我就介紹稍微小眾一些的演算法--參數演算法(Parameterized Algorithm)。

在解決NP難的問題時，為了能處理海量數據，會退而求其次選擇啟發式演算法，近似演算法，隨機演算法等非精確演算法，雖然能使時間複雜度降低到多項式級別，但是得到的結果是近似的，哪怕是PTAS的演算法。相當多的問題要求必須得到精確解，近似解是沒有意義的。這就需要參數演算法出場了。

NP難的問題時間複雜度都是指數，將所有可能全部遍歷一次的時間複雜度是 $2^{n}$ ，很多時候我們最後得到的解集大小 $k$ 和總輸入大小 $n$ 相差很多，所以想到將指數 $n$ 降低到解集大小 $k$ ，也就是把複雜度從 $O(2^n)$ 降低到 $O(n^C*2^k)$ ，這樣我們能夠處理的數據就更多了呢。但是，不是所有NP難的問題都能使用參數演算法解決，能解決的被稱為FPT(Fixed-Parameter Tractable)，不能的就很遺憾了，就要把這些問題歸屬到W-hard，又根據難度的不同分為W[1]-HARD，W[2]-HARD等等，大多數就這兩個等級，例如著名的最大團問題(Maximal Clique)，獨立集問題(Independent Set)都屬於W[1]-HARD，維基百科上有介紹。

好像扯遠了，回到FPT上吧，從Richard M. Karp的21個問題[1](8000多的引用啊！)出發，包括後來出現的一些新的經典問題，規約關係如下圖：

恩。最開始被證明是NP-Complete的問題是3-SAT問題，其他的做規約就可以了。

說個邊支配集問題(Edge Dominating Set)吧

最開始被MR Garey和DS Johnson證明NPC問題[2](那個時候證明NPC是很時髦的啊，能發很好的Journal啊)
又被Yannakakis和Gavril證明在最大度為3的二分圖中依然是NPC的[3]。
最新的成果是在2012年，在一般圖和3度圖中的時間複雜度分別為 $O(2.4181^k)$ 和 $O(2.1479^k)$

Reference:

[1]R. M. Karp, Reducibility among combinatorial problems. Springer, 1972.

[2]M. R. Garey and D. S. Johnson, 「The rectilinear Steiner tree problem is NP-complete,」 SIAM Journal on Applied Mathematics, vol. 32, no. 4, pp. 826–834, 1977.

[3]M. Yannakakis and F. Gavril, 「Edge dominating sets in graphs,」 SIAM Journal on Applied Mathematics, vol. 38, no. 3, pp. 364–372, 1980.

p == or != NP

排序(經典的快速排序，歸併排序，堆排序，冒泡，插入，選擇，希爾排序等)，查找(線性查找，二叉查找樹，哈希)，貪婪演算法，動態規劃(背包，矩陣鏈乘等)，搜索(BFS,DFS, A*)，單源最短路徑，最小生成樹，並查集等等

最著名的應該是旅行商問題。還有高德納老爺子能不能活著完成他的曠世名著。。

分治，最長上升子序列問題，還有各種樹，圖論

我也來一個，經典的圓周率pi計算演算法，4行語句：

#include &
#define MAX_C 56000 //計算800位
int a=10000,b,c=MAX_C,d,e,f[MAX_C+1],g;
main()

{
for(;b-c;) f[b++]=a/5;
for(;d=0,g=c*2;c -=14,printf("%.4d",e+d/a),e=d%a)
for(b=c; d+=f[b]*a,f[b]=d%--g,d/=g--,--b; d*=b);
getch();

}

我很懶……所以匿名吧……

NPC問題_百度百科

求最小獨立邊支配集的演算法

我先想到的是七橋問題。。。

3n+1

漢諾塔問題