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

目錄

第1章　引言　　1
1.1　編程競賽　　1
1.1.1　線上學(xué)習(xí)網(wǎng)站　　3
1.1.2　線上裁判的返回值　　4
1.2　我們的選擇：Python　　5
1.3　輸入輸出　　6
1.3.1　讀取標(biāo)準(zhǔn)輸入　　6
1.3.2　顯示格式　　9
1.4　復(fù)雜度　　9
1.5　抽象類型和基本數(shù)據(jù)結(jié)構(gòu)　　11
1.5.1　?！　?1
1.5.2　字典　　12
1.5.3　隊(duì)列　　12
1.5.4　優(yōu)先級(jí)隊(duì)列和最小堆　　13
1.5.5　并查集　　16
1.6　技術(shù)　　18
1.6.1　比較　　18
1.6.2　排序　　18
1.6.3　掃描　　19
1.6.4　貪婪算法　　20
1.6.5　動(dòng)態(tài)規(guī)劃算法　　20
1.6.6　用整數(shù)編碼集合　　21
1.6.7　二分查找　　23
1.7　建議　　25
1.8　走得更遠(yuǎn)　　27
第2章　字符串　　28
2.1　易位構(gòu)詞　　28
2.2　T9：9 個(gè)按鍵上的文字　　29
2.3　使用字典樹進(jìn)行拼寫糾正　　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)的重復(fù)內(nèi)容　　54
4.4　區(qū)間的最大總和　　55
4.5　查詢區(qū)間中的最小值：線段樹　　55
4.6　計(jì)算區(qū)間的總和：樹狀數(shù)組（Fenwick 樹）　　57
4.7　有k 個(gè)獨(dú)立元素的窗口　　59
第5章　區(qū)間　　61
5.1　區(qū)間樹（線段樹）　　61
5.2　區(qū)間的并集　　64
5.3　區(qū)間的覆蓋　　64
第6章　圖　　66
6.1　使用Python 對(duì)圖編碼　　66
6.2　使用C++ 或Java 對(duì)圖編碼　　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　拓?fù)渑判颉　?7
6.9　強(qiáng)連通分量　　79
6.10　可滿足性　　84
第7章　圖中的環(huán)　　86
7.1　歐拉路徑　　86
7.2　中國郵差問題　　88
7.3　最小長度上的比率權(quán)重環(huán)：Karp 算法　　89
7.4　單位時(shí)間成本最小比率環(huán)　　92
7.5　旅行推銷員問題　　93
第8章　最短路徑　　94
8.1　組合的屬性　　94
8.2　權(quán)重為0 或1 的圖　　96
8.3　權(quán)重為正值或空值的圖： Dijkstra 算法　　97
8.4　隨機(jī)權(quán)重的圖：Bellman-Ford 算法　　100
8.5　所有源點(diǎn)- 目標(biāo)頂點(diǎn)對(duì)：Floyd-Warshall 算法　　101
8.6　網(wǎng)格　　102
8.7　變種問題　　104
8.7.1　無權(quán)重圖　　104
8.7.2　有向無環(huán)圖　　104
8.7.3　最長路徑　　104
8.7.4　樹中的最長路徑　　104
8.7.5　最小化弧上權(quán)重的路徑　　105
8.7.6　頂點(diǎn)有權(quán)重的圖　　105
8.7.7　令頂點(diǎn)上最大權(quán)重最小的路徑　　105
8.7.8　所有邊都屬于一條最短路徑　　105
第9章　耦合性和流　　106
9.1　二分圖最大匹配　　107
9.2　最大權(quán)重的完美匹配： 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　運(yùn)輸問題　　127
9.11　在流和匹配之間化簡　　127
9.12　偏序的寬度：Dilworth 算法　　129
第10章　樹　　132
10.1　哈夫曼編碼　　133
10.2　最近的共同祖先　　135
10.3　樹中的最長路徑　　138
10.4　最小權(quán)重生成樹：Kruskal 算法　　140
第11章　集合　　142
11.1　背包問題　　142
11.2　找零問題　　143
11.3　給定總和值的子集　　145
11.4　k 個(gè)整數(shù)之和　　146
第12章　點(diǎn)和多邊形　　148
12.1　凸包問題　　149
12.2　多邊形的測量　　150
12.3　最近點(diǎn)對(duì)　　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章　計(jì)算　　165
14.1　最大公約數(shù)　　165
14.2　貝祖等式　　165
14.3　二項(xiàng)式系數(shù)　　166
14.4　快速求冪　　167
14.5　素?cái)?shù)　　167
14.6　計(jì)算算數(shù)表達(dá)式　　168
14.7　線性方程組　　170
14.8　矩陣序列相乘　　174
第15章　窮舉　　176
15.1　激光路徑　　176
15.2　精確覆蓋　　179
15.3　數(shù)獨(dú)　　184
15.4　排列枚舉　　186
15.5　正確計(jì)算　　188
調(diào)試工具　　191
參考文獻(xiàn)　　192