高效算法：競(jìng)賽、應(yīng)試與提高必修128例

定　價(jià)：￥55.00

作　者：	[法] 克里斯托弗·杜爾（Christoph Dürr）著，史世強(qiáng) 譯
出版社：	人民郵電出版社
叢編項(xiàng)：	圖靈程序設(shè)計(jì)叢書(shū)
標(biāo)　簽：	暫缺

購(gòu)買(mǎi)這本書(shū)可以去

ISBN：	9787115480859	出版時(shí)間：	2018-05-01	包裝：	平裝
開(kāi)本：	16開(kāi)	頁(yè)數(shù)：	193	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

　　Christoph Dürr，法國(guó)國(guó)家科學(xué)研究院研究員，巴黎皮埃爾-瑪麗·居里大學(xué)博士生導(dǎo)師，Operation Research科研組研究主任。Jill-Jênn Vie，法國(guó)高等電力學(xué)院博士、算法講師，擔(dān)任法國(guó)高等師范學(xué)院Paris-Saclay團(tuán)隊(duì)在ACM競(jìng)賽中的算法導(dǎo)師；曾任法國(guó)國(guó)際編程大賽Prologin主席，并于2014年獲Google RISE Award。

圖書(shū)目錄

第 1 章引言 1
1 1 編程競(jìng)賽 1
1 1 1 線(xiàn)上學(xué)習(xí)網(wǎng)站 3
1 1 2 線(xiàn)上裁判的返回值 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 抽象類(lèi)型和基本數(shù)據(jù)結(jié)構(gòu) 11
1 5 1 棧 11
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 使用字典樹(shù)進(jìn)行拼寫(xiě)糾正 31
2 4 KMP（Knuth-Morris-Pratt）模式匹配算法 33
2 5 最大邊的 KMP 算法 35
2 6 字符串的冪 38
2 7 模式匹配算法：Rabin–Karp 算法 38
2 8 字符串的最長(zhǎng)回文子串：Manacher 算法 42
第 3 章序列 44
3 1 網(wǎng)格中的最短路徑 44
3 2 編輯距離（列文斯登距離45
3 3 最長(zhǎng)公共子序列 47
3 4 升序最長(zhǎng)子序列 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 查詢(xún)區(qū)間中的最小值：線(xiàn)段樹(shù) 55
4 6 計(jì)算區(qū)間的總和：樹(shù)狀數(shù)組（Fenwick 樹(shù)）57
4 7 有 k 個(gè)獨(dú)立元素的窗口 59
第 5 章區(qū)間 61
5 1 區(qū)間樹(shù)（線(xiàn)段樹(shù)） 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ù)渑判?77
6 9 強(qiáng)連通分量 79
6 10 可滿(mǎn)足性 84
第 7 章圖中的環(huán) 86
7 1 歐拉路徑 86
7 2 中國(guó)郵差問(wèn)題 88
7 3 最小長(zhǎng)度上的比率權(quán)重環(huán)：Karp 算法 89
7 4 單位時(shí)間成本最小比率環(huán) 92
7 5 旅行推銷(xiāo)員問(wèn)題 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 變種問(wèn)題 104
8 7 1 無(wú)權(quán)重圖 104
8 7 2 有向無(wú)環(huán)圖 104
8 7 3 最長(zhǎng)路徑 104
8 7 4 樹(shù)中的最長(zhǎng)路徑 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 無(wú)交叉平面匹配 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)輸問(wèn)題 127
9 11 在流和匹配之間化簡(jiǎn) 127
9 12 偏序的寬度：Dilworth 算法 129
第 10 章樹(shù) 132
10 1 哈夫曼編碼 133
10 2 最近的共同祖先 135
10 3 樹(shù)中的最長(zhǎng)路徑 138
10 4 最小權(quán)重生成樹(shù)：Kruskal 算法 140
第 11 章集合 142
11 1 背包問(wèn)題 142
11 2 找零問(wèn)題 143
11 3 給定總和值的子集 145
11 4 k 個(gè)整數(shù)之和 146
第 12 章點(diǎn)和多邊形 148
12 1 凸包問(wèn)題 149
12 2 多邊形的測(cè)量 150
12 3 最近點(diǎn)對(duì) 151
12 4 簡(jiǎn)單直線(xiàn)多邊形 153
第 13 章長(zhǎng)方形 156
13 1 組成長(zhǎng)方形 156
13 2 網(wǎng)格中的最大正方形 157
13 3 直方圖中的最大長(zhǎng)方形 158
13 4 網(wǎng)格中的最大長(zhǎng)方形 159
13 5 合并長(zhǎng)方形 160
13 6 不相交長(zhǎng)方形的合并 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 線(xiàn)性方程組 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