●致謝
一夜春風,萬樹梨花
第00章 開篇緒言
緣起
預備知識
第01章 思想與實現
思想
實現
準備一棵樹
用遞推代碼實現遞推思想
用遞歸代碼實現遞推思想
用遞歸代碼實現遞歸思想
“好”的遞歸與“壞”的遞歸
用遞推代碼實現遞歸思想
思考題
第02章 回溯:上古神話中的算法
回溯式遞歸的基本原理
示例1
示例2
神話故事中的算法
迷宮設計入門
探尋迷宮中的路徑
用遞推(循環)代碼實現回溯
思考題
第03章 動態規劃:動機決定性質
什麼是動態規劃
透徹理解動態規劃
遞推版動態規劃
遞歸版動態規劃
陷阱:這不是動態規劃
貪心也要動腦子
更上層樓:讓規劃“動態”起來
切年糕
接訂單
聽講座
思考題
動態規劃哲思
第04章 排序:算法皇冠上的明珠
遊樂園:O(n2)的簡單排序們
選擇排序
冒泡排序
插入排序
以空間換時間:歸並排序
看運氣的快速排序
兩全其美:堆排序
什麼是“堆”
構建大/小根堆
利用“大根堆”進行原地排序
利用“小根堆”生成升序數組
思考題
第05章 查找:來而不往非禮也
二分查找
在己排序的數組上
在平衡二叉搜索樹上
線段樹:化繁為簡
構建線段樹
查詢子段和
字典樹:字母大接龍
遞推版實現
遞歸版實現
並查集:朋友的朋友是朋友
第06章 圖:包羅萬像
圖的表達
鄰接列表
鄰接矩陣
應對向、權、環的變化
思考題
圖的遍歷
廣度優先遍歷
深度優先遍歷
遞推版深度優先遍歷
向、權、環對遍歷的影響
頂點的連通性
有無權重對連通性的影響
有無向對連通性的影響
環對連通性的影響
強連通性組件
Kosaraju-Sharir算法
圖上的路徑
BFS式路徑搜尋
DFS式路徑搜尋
自底向上式路徑搜尋
回溯式路徑搜尋
獲取環路
思考題
最短路徑
Dijkstra最短路徑算法
Bellman-Ford最短路徑算法
Floyd-Warshall最短路徑算法
最小生成樹
構建有權無向圖
Prim算法
Kruskal算法
優選流:超時空移花接木
餘量邊,反向邊,餘量網絡,增益路徑
容量返還
Ford-Fulkerson算法實現
最小割:流量的瓶頸
拓撲排序
生成入度圖與出度圖
理解頂點的入度
遞推實現
遞歸實現
思考題
後記
算法是個有趣的東西——針對某個問題設計算法的時候,不會的人感覺像“大海撈針”,而會的人則感覺像“一葦渡江”。高手的頭腦裡都有一張“算法地圖”,算法之間不是孤立的,而是彼此連通的。算法之間的內在聯繫有很多,但挖掘到根源上,就是遞推與遞歸兩種思想。本書從深度解析遞推和遞歸這兩個基本算法思想開始,用它們貫穿起了《算法導論》中的幾十個經典算法,包括排序、查找、回溯、貪心、分治、動態規劃、圖算法等。 本書成稿自作者的教案,秉承了作者一貫的風趣幽默又不失嚴謹的寫作風格,同時融入了學習心理學和認知科學的實踐原理。作者的諸多學生在參加完以本書內容為藍本的集訓後進入了微軟、臉書、亞馬遜、領英、甲骨文等公司,所以本書是經過千錘百煉的一線教學成果。本書適合於所有想通過學習算法來精進自己編程能力的讀者。為了傾聽讀者們的心聲、不斷完善這本書,作者熱切地期待大家與他在領英上建立聯繫。在那裡,作者還將源源不等