本書旨在探討如何優(yōu)化算法效率，詳細闡述了經(jīng)典算法和特殊算法的實現(xiàn)、應用技巧和復雜度驗證過程，內(nèi)容由淺入深，能幫助讀者快速掌握復雜度適當、正確率高的高效編程方法以及自檢、自測技巧，是參加ACM/ICPC、Google Code Jam 等國際編程競賽、備戰(zhàn)編程考試、提高編程效率、優(yōu)化編程方法的參考書目。

目錄

第1章　引言　　1
1.1　編程競賽　　1
1.1.1　線上學習網(wǎng)站　　3
1.1.2　線上裁判的返回值　　4
1.2　我們的選擇：Python　　5
1.3　輸入輸出　　6
1.3.1　讀取標準輸入　　6
1.3.2　顯示格式　　9
1.4　復雜度　　9
1.5　抽象類型和基本數(shù)據(jù)結構　　11
1.5.1　?！　?1
1.5.2　字典　　12
1.5.3　隊列　　12
1.5.4　優(yōu)先級隊列和最小堆　　13
1.5.5　并查集　　16
1.6　技術　　18
1.6.1　比較　　18
1.6.2　排序　　18
1.6.3　掃描　　19
1.6.4　貪婪算法　　20
1.6.5　動態(tài)規(guī)劃算法　　20
1.6.6　用整數(shù)編碼集合　　21
1.6.7　二分查找　　23
1.7　建議　　25
1.8　走得更遠　　27
第2章　字符串　　28
2.1　易位構詞　　28
2.2　T9：9 個按鍵上的文字　　29
2.3　使用字典樹進行拼寫糾正　　31
2.4　KMP（Knuth-Morris-Pratt）模式匹配算法　　33
2.5　最大邊的KMP 算法　　35
2.6　字符串的冪　　38
2.7　模式匹配算法：Rabin–Karp 算法　　38
2.8　字符串的最長回文子串：Manacher 算法　　42
第3章　序列　　44
3.1　網(wǎng)格中的最短路徑　　44
3.2　編輯距離（列文斯登距離）　　45
3.3　最長公共子序列　　47
3.4　升序最長子序列　　49
3.5　兩位玩家游戲中的必勝策略　　52
第4章　數(shù)組　　53
4.1　合并已排序列表　　53
4.2　區(qū)間的總和　　54
4.3　區(qū)間內(nèi)的重復內(nèi)容　　54
4.4　區(qū)間的最大總和　　55
4.5　查詢區(qū)間中的最小值：線段樹　　55
4.6　計算區(qū)間的總和：樹狀數(shù)組（Fenwick 樹）　　57
4.7　有k 個獨立元素的窗口　　59
第5章　區(qū)間　　61
5.1　區(qū)間樹（線段樹）　　61
5.2　區(qū)間的并集　　64
5.3　區(qū)間的覆蓋　　64
第6章　圖　　66
6.1　使用Python 對圖編碼　　66
6.2　使用C++ 或Java 對圖編碼　　67
6.3　隱式圖　　68
6.4　深度優(yōu)先遍歷：深度優(yōu)先算法　　69
6.5　廣度優(yōu)先遍歷：廣度優(yōu)先算法　　70
6.6　連通分量　　71
6.7　雙連通分量　　74
6.8　拓撲排序　　77
6.9　強連通分量　　79
6.10　可滿足性　　84
第7章　圖中的環(huán)　　86
7.1　歐拉路徑　　86
7.2　中國郵差問題　　88
7.3　最小長度上的比率權重環(huán)：Karp 算法　　89
7.4　單位時間成本最小比率環(huán)　　92
7.5　旅行推銷員問題　　93
第8章　最短路徑　　94
8.1　組合的屬性　　94
8.2　權重為0 或1 的圖　　96
8.3　權重為正值或空值的圖： Dijkstra 算法　　97
8.4　隨機權重的圖：Bellman-Ford 算法　　100
8.5　所有源點- 目標頂點對：Floyd-Warshall 算法　　101
8.6　網(wǎng)格　　102
8.7　變種問題　　104
8.7.1　無權重圖　　104
8.7.2　有向無環(huán)圖　　104
8.7.3　最長路徑　　104
8.7.4　樹中的最長路徑　　104
8.7.5　最小化弧上權重的路徑　　105
8.7.6　頂點有權重的圖　　105
8.7.7　令頂點上最大權重最小的路徑　　105
8.7.8　所有邊都屬于一條最短路徑　　105
第9章　耦合性和流　　106
9.1　二分圖最大匹配　　107
9.2　最大權重的完美匹配： Kuhn-Munkres 算法　　110
9.3　無交叉平面匹配　　116
9.4　穩(wěn)定的婚姻：Gale-Shapley 算法　　117
9.5　Ford-Fulkerson 最大流算法　　119
9.6　Edmonds-Karp 算法的最大流　　121
9.7　Dinic 最大流算法　　122
9.8　s-t 最小割　　125
9.9　平面圖的s-t 最小割　　126
9.10　運輸問題　　127
9.11　在流和匹配之間化簡　　127
9.12　偏序的寬度：Dilworth 算法　　129
第10章　樹　　132
10.1　哈夫曼編碼　　133
10.2　最近的共同祖先　　135
10.3　樹中的最長路徑　　138
10.4　最小權重生成樹：Kruskal 算法　　140
第11章　集合　　142
11.1　背包問題　　142
11.2　找零問題　　143
11.3　給定總和值的子集　　145
11.4　k 個整數(shù)之和　　146
第12章　點和多邊形　　148
12.1　凸包問題　　149
12.2　多邊形的測量　　150
12.3　最近點對　　151
12.4　簡單直線多邊形　　153
第13章　長方形　　156
13.1　組成長方形　　156
13.2　網(wǎng)格中的最大正方形　　157
13.3　直方圖中的最大長方形　　158
13.4　網(wǎng)格中的最大長方形　　159
13.5　合并長方形　　160
13.6　不相交長方形的合并　　164
第14章　計算　　165
14.1　最大公約數(shù)　　165
14.2　貝祖等式　　165
14.3　二項式系數(shù)　　166
14.4　快速求冪　　167
14.5　素數(shù)　　167
14.6　計算算數(shù)表達式　　168
14.7　線性方程組　　170
14.8　矩陣序列相乘　　174
第15章　窮舉　　176
15.1　激光路徑　　176
15.2　精確覆蓋　　179
15.3　數(shù)獨　　184
15.4　排列枚舉　　186
15.5　正確計算　　188
調(diào)試工具　　191
參考文獻　　192