123,123

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

　　算法是個(gè)有趣的東西—針對(duì)某個(gè)問題設(shè)計(jì)算法的時(shí)候，不會(huì)的人感覺像“大海撈針”，而會(huì)的人則感覺像“一葦渡江”。高手的頭腦里都有一張“算法地圖”，算法之間不是孤立的，而是彼此連通的。算法之間的內(nèi)在聯(lián)系有很多，但挖掘到根源上，就是遞推與遞歸兩種思想。本書從深度解析遞推和遞歸這兩個(gè)基本算法思想開始，用它們貫穿起了《算法導(dǎo)論》中的幾十個(gè)經(jīng)典算法，包括排序、查找、回溯、貪心、分治、動(dòng)態(tài)規(guī)劃、圖算法等。本書成稿自作者的教案，秉承了作者一貫的風(fēng)趣幽默又不失嚴(yán)謹(jǐn)?shù)膶懽黠L(fēng)格，同時(shí)融入了學(xué)習(xí)心理學(xué)和認(rèn)知科學(xué)的實(shí)踐原理。作者的諸多學(xué)生在參加完以本書內(nèi)容為藍(lán)本的集訓(xùn)后進(jìn)入了微軟、臉書、亞馬遜、領(lǐng)英、甲骨文等公司，所以本書是經(jīng)過千錘百煉的一線教學(xué)成果。本書適合于所有想通過學(xué)習(xí)算法來精進(jìn)自己編程能力的讀者。為了傾聽讀者們的心聲、不斷完善這本書，作者熱切地期待大家與他在領(lǐng)英上建立聯(lián)系。在那里，作者還將源源不斷地與讀者們分享種類教學(xué)資源和工作機(jī)會(huì)。作者的領(lǐng)英首頁(yè)是https：www.linkedin.cominhexagons。

作者簡(jiǎn)介

　　劉鐵猛，高級(jí)軟件工程師，技術(shù)作者、譯者、教育者，現(xiàn)就職于亞馬遜（美國(guó)）。曾就職于微軟（美國(guó)），著有《深入淺出WPF》一書，銷量數(shù)萬冊(cè)。精心制作的《C#語言入門詳解》視頻課程點(diǎn)擊量超500萬次，是目前全球排名*一的中文C#教程。他的多套視頻教學(xué)已被微軟收錄為官方認(rèn)證課程。他的所有作品風(fēng)格一致：內(nèi)容詳實(shí)準(zhǔn)確、語言風(fēng)趣幽默、說理深入淺出，被學(xué)習(xí)者們奉為佳作。

圖書目錄

致謝
一夜春風(fēng)，萬樹梨花
第00章開篇緒言
緣起 1
預(yù)備知識(shí) 3
第01章思想與實(shí)現(xiàn)
思想 6
實(shí)現(xiàn) 8
準(zhǔn)備一棵樹 9
用遞推代碼實(shí)現(xiàn)遞推思想 11
用遞歸代碼實(shí)現(xiàn)遞推思想 13
用遞歸代碼實(shí)現(xiàn)遞歸思想 15
“好”的遞歸與“壞”的遞歸 16
用遞推代碼實(shí)現(xiàn)遞歸思想 20
思考題 23
第02章  回溯：上古神話中的算法
回溯式遞歸的基本原理 24
示例1 25
示例2 26
神話故事中的算法 27
迷宮設(shè)計(jì)入門 28
探尋迷宮中的路徑 29
用遞推（循環(huán)）代碼實(shí)現(xiàn)回溯 32
思考題 33
第03章  動(dòng)態(tài)規(guī)劃：動(dòng)機(jī)決定性質(zhì)
什么是動(dòng)態(tài)規(guī)劃 35
透徹理解動(dòng)態(tài)規(guī)劃 36
遞推版動(dòng)態(tài)規(guī)劃 37
遞歸版動(dòng)態(tài)規(guī)劃 39
陷阱：這不是動(dòng)態(tài)規(guī)劃！ 42
貪心也要?jiǎng)幽X子 43
更上層樓：讓規(guī)劃“動(dòng)態(tài)”起來 46
切年糕 46
接訂單 48
聽講座 56
思考題 60
動(dòng)態(tài)規(guī)劃哲思 60
第04章  排序：算法皇冠上的明珠
游樂園：O(n^2)的簡(jiǎn)單排序們 63
選擇排序 63
冒泡排序 64
插入排序 66
以空間換時(shí)間：歸并排序 66
看運(yùn)氣的快速排序 68
兩全其美：堆排序 71
什么是“堆” 71
構(gòu)建大/小根堆 72
利用“大根堆”進(jìn)行原地排序 75
利用“小根堆”生成升序數(shù)組 75
思考題 76
第05章  查找：來而不往非禮也
二分查找 78
在已排序的數(shù)組上 79
在平衡二叉搜索樹上 80
線段樹：化繁為簡(jiǎn) 81
構(gòu)建線段樹 82
查詢子段和 84
字典樹：字母大接龍 86
遞推版實(shí)現(xiàn) 87
遞歸版實(shí)現(xiàn) 89
并查集：朋友的朋友是朋友 90
第06章  圖：包羅萬象
圖的表達(dá) 94
鄰接列表 95
鄰接矩陣 97
應(yīng)對(duì)向、權(quán)、環(huán)的變化 98
思考題 100
圖的遍歷 100
廣度優(yōu)先遍歷 101
深度優(yōu)先遍歷 103
遞推版深度優(yōu)先遍歷 105
向、權(quán)、環(huán)對(duì)遍歷的影響 106
頂點(diǎn)的連通性 107
有無權(quán)重對(duì)連通性的影響 109
有無向?qū)B通性的影響 110
環(huán)對(duì)連通性的影響 113
強(qiáng)連通性組件 113
Kosaraju-Sharir算法 114
圖上的路徑 116
BFS式路徑搜尋 118
DFS式路徑搜尋 119
自底向上式路徑搜尋 119
回溯式路徑搜尋 121
獲取環(huán)路 122
思考題 123
短路徑 124
Dijkstra短路徑算法 125
Bellman-Ford短路徑算法 129
Floyd-Warshall短路徑算法 131
小生成樹 133
構(gòu)建有權(quán)無向圖 134
Prim算法 136
Kruskal算法 137
流：超時(shí)空移花接木 138
余量邊，反向邊，余量網(wǎng)絡(luò)，增益路徑 139
容量返還 140
Ford-Fulkerson算法實(shí)現(xiàn) 143
小割：流量的瓶頸 145
拓?fù)渑判?147
生成入度圖與出度圖 148
理解頂點(diǎn)的入度 149
遞推實(shí)現(xiàn) 150
遞歸實(shí)現(xiàn) 151
思考題 152
后記