第1章 算法初步 1 1.1　什么是算法　1 1.1.1　算法的定義　1 1.1.2　算法與程序的區(qū)別　1 1.2　時間復(fù)雜度　2 1.2.1　運行時間和程序復(fù)雜程度的 關(guān)系　2 1.2.2　時間復(fù)雜度是漸進的　2 1.2.3　簡單程序的時間復(fù)雜度分析　3 1.2.4　時間復(fù)雜度的意義　6 1.3　空間復(fù)雜度　8 1.4　算法的應(yīng)用　8 1.5　Python算法的優(yōu)勢　9 1.6　小結(jié)　9 1.7　習(xí)題　10 第2章　排序算法　12 2.1　初級排序算法　12 2.1.1　插入排序　12 2.1.2　選擇排序　14 2.1.3　冒泡排序　17 2.2　高級排序算法　19 2.2.1　歸并排序　19 2.2.2　快速排序　21 2.2.3　希爾排序　24 2.2.4　堆排序　26 2.2.5　桶排序　30 2.3　小結(jié)　32 2.4　習(xí)題　32 第3章　查找　34 3.1　順序查找　34 3.2　二分查找　35 3.3　樹　41 3.4　二叉樹　43 3.4.1　二叉樹的性質(zhì)　43 3.4.2　滿二叉樹　44 3.4.3　完全二叉樹　44 3.4.4　創(chuàng)建二叉樹　45 3.4.5　遍歷二叉樹　46 3.5　二叉搜索樹　47 3.5.1　二叉搜索樹基礎(chǔ)　47 3.5.2　二叉搜索樹的操作　47 3.6　平衡二叉樹　56 3.6.1　二叉搜索樹的效率　56 3.6.2　AVL樹　56 3.7　小結(jié)　62 3.8　習(xí)題　62 第4章　雙指針問題　65 4.1　單鏈表　65 4.1.1　建立單鏈表　65 4.1.2　遍歷單鏈表　66 4.1.3　插入單鏈表　66 4.1.4　刪除單鏈表第n個數(shù)　68 4.2　雙指針的應(yīng)用　69 4.2.1　數(shù)組合并問題　69 4.2.2　刪除單鏈表倒數(shù)第n個數(shù)　71 4.3　小結(jié)　72 4.4　習(xí)題　72 第5章　哈希算法　73 5.1　哈希算法的原理　73 5.2　哈希函數(shù)　74 5.2.1　除法哈希算法　74 5.2.2　乘法哈希算法　75 5.2.3　平方取中法　75 5.2.4　隨機數(shù)哈希算法　75 5.3　解決沖突　76 5.3.1　開放定址法　76 5.3.2　拉鏈址法　77 5.4　哈希算法的應(yīng)用　78 5.4.1　兩個數(shù)的和問題　78 5.4.2　團體賽問題　79 5.4.3　猜數(shù)字游戲　81 5.5　小結(jié)　83 5.6　習(xí)題　83 第6章　深度優(yōu)先搜索算法　85 6.1　搜索　85 6.2　圖上的深度優(yōu)先搜索　85 6.2.1　無向圖　85 6.2.2　圖的術(shù)語　86 6.2.3　圖上的搜索　88 6.2.4　經(jīng)典例題講解（最大的油田）　89 6.3　二叉樹上的深度優(yōu)先搜索　91 6.3.1　二叉樹相關(guān)術(shù)語　91 6.3.2　二叉樹上的搜索　92 6.3.3　經(jīng)典例題講解（員工派對）　92 6.3.4　經(jīng)典例題講解（城市危機）　97 6.4　小結(jié)　105 6.5　習(xí)題　106 第7章　廣度優(yōu)先搜索算法　107 7.1　依舊是圖的搜索　107 7.2　隊列中的存儲方式　108 7.3　經(jīng)典例題講解　111 7.3.1　艱難旅行　111 7.3.2　混亂地鐵　114 7.3.3　溫室大棚　116 7.4　小結(jié)　120 7.5　習(xí)題　120 第8章　回溯算法　121 8.1　回溯算法原理　121 8.2　回溯算法的應(yīng)用　124 8.2.1　N皇后　124 8.2.2　數(shù)獨　128 8.2.3　排列組合　132 8.2.4　兩個擴展問題　137 8.3　小結(jié)　139 8.4　習(xí)題　139 第9章　動態(tài)規(guī)劃　141 9.1　動態(tài)規(guī)劃介紹　141 9.2　礦工問題　141 9.2.1　問題描述　141 9.2.2　問題分析　142 9.2.3　參考實現(xiàn)　145 9.3　爬樓梯問題　146 9.3.1　問題描述　146 9.3.2　問題分析　147 9.3.3　參考實現(xiàn)　149 9.4　背包問題　149 9.4.1　問題描述　149 9.4.2　問題分析　150 9.4.3　問題實例　151 9.4.4　參考實現(xiàn)　153 9.5　最長遞增子序列問題　154 9.5.1　問題描述　154 9.5.2　改進算法　155 9.5.3　參考實現(xiàn)　156 9.6　小結(jié)　157 9.7　習(xí)題　157 第10章　貪心算法　158 10.1　貪心算法介紹　158 10.2　硬幣找零問題　159 10.2.1　問題描述　159 10.2.2　問題實例　159 10.2.3　參考實現(xiàn)　160 10.3　活動安排問題　160 10.3.1　問題描述　160 10.3.2　參考實現(xiàn)　161 10.4　哈夫曼編碼　162 10.4.1　問題描述　163 10.4.2　哈夫曼樹　163 10.4.3　貪心選擇性質(zhì)　165 10.4.4　最優(yōu)子結(jié)構(gòu)性質(zhì)　166 10.4.5　參考實現(xiàn)　166 10.5　小結(jié)　167 10.6　習(xí)題　168 第11章　分治算法　169 11.1　分治算法原理　169 11.2　分治算法應(yīng)用　170 11.2.1　二分查找　170 11.2.2　二維數(shù)組的查找　171 11.2.3　快速凸包算法　173 11.2.4　快速傅氏變換　178 11.3　小結(jié)　183 11.4　習(xí)題　183 第12章　并查集　184 12.1　并查集介紹　184 12.1.1　并查集的構(gòu)造方法　184 12.1.2　并查集的應(yīng)用　184 12.1.3　并查集3種基本操作的Python實現(xiàn)　186 12.2　朋友圈　187 12.2.1　問題描述　187 12.2.2　問題分析　187 12.2.3　代碼　188 12.3　圖的子元素　190 12.3.1　問題描述　190 12.3.2　問題分析　190 12.3.3　代碼　192 12.4　小結(jié)　193 12.5　習(xí)題　193 第13章　最短路徑算法　194 13.1　戴克斯特拉算法　194 13.1.1　算法介紹　194 13.1.2　算法證明　199 13.1.3　算法代碼　200 13.2　貝爾曼-福特算法　202 13.2.1　算法介紹　203 13.2.2　算法證明　205 13.2.3　算法代碼　206 13.3　弗洛伊德算法　208 13.3.1　算法介紹　208 13.3.2　算法代碼　212 13.4　A*搜索算法　215 13.4.1　算法介紹　215 13.4.2　算法證明　219 13.4.3　算法代碼　220 13.5　習(xí)題　222 第14章　數(shù)論算法　223 14.1　歐幾里得算法　223 14.1.1　算法分析與證明　223 14.1.2　算法代碼　224 14.1.3　算法應(yīng)用　224 14.2　中國余數(shù)定理　228 14.2.1　算法介紹　228 14.2.2　算法證明　229 14.2.3　算法代碼　229 14.3　素性檢驗算法　230 14.3.1　費馬素性檢驗　230 14.3.2　米勒-拉賓素性檢驗　231 14.3.3　算法代碼　233 14.4　小結(jié)　234 14.5　習(xí)題　234