算法設計與分析基礎（Python語言描述）（微課視頻版）

李春葆，武漢大學計算機學院教授。主要研究方向為數據挖掘和算法設計，先後主持和參加多個大型研究項目。主要為本科生講授數據結構（15年以上）和軟件工程等課程，為研究生講授軟件開發新技術、數據倉庫與數據挖掘等課程，並出版十多部精品著作。

 

目錄

 

 

 

 

掃一掃

 

 

 

源碼下載

 

 

 

第1章算法入門——概論/

 

1．1算法概述/

 

1．1．1什麽是算法/

 

1．1．2算法的描述/

 

1．1．3算法設計的基本步驟/

 

1．2算法分析/

 

1．2．1算法的時間復雜度分析/

 

1．2．2算法的空間復雜度分析/

 

習題1/

 

第2章工之利器——常用數據結構及其應用/

 

2．1線性表——數組/

 

2．1．1線性表的定義/

 

2．1．2Python列表/

 

2．1．3列表元素的排序/

 

2．1．4列表的復制/

 

2．1．5實戰——移除元素(LeetCode27★)/

 

2．2線性表——鏈表/

 

2．2．1單鏈表/

 

2．2．2實戰——反轉鏈表(LeetCode206★)/

 

2．3字符串/

 

2．3．1字符串的定義/

 

2．3．2Python中的字符串/

 

2．3．3實戰——最大重復子字符串(LeetCode1668★)/

 

2．4棧/

 

2．4．1棧的定義/

 

2．4．2用Python列表實現棧/

 

2．4．3實戰——使括號有效的最少添加

(LeetCode921★★)/

 

2．5雙端隊列/

 

2．5．1雙端隊列的定義/

 

2．5．2Python中的雙端隊列/

 

2．5．3實戰——滑動窗口中的最大值

(LeetCode239★★★)/

 

2．6隊列/

 

2．6．1隊列的定義/

 

2．6．2Python中的隊列/

 

2．6．3實戰——無法吃午餐的學生的數量

(LeetCode1700★)/

 

2．7優先隊列/

 

2．7．1優先隊列的定義/

 

2．7．2Python中的優先隊列/

 

2．7．3實戰——數據流中第k大的元素

(LeetCode703★)/

 

2．8樹和二叉樹/

 

2．8．1樹/

 

2．8．2二叉樹/

 

2．8．3實戰——二叉樹的完全性檢驗

(LeetCode958★★)/

 

2．9圖/

 

2．9．1圖的基礎/

 

2．9．2實戰——課程表(LeetCode207★★)/

 

2．10並查集/

 

2．10．1並查集的基礎/

 

2．10．2實戰——省份的數量(LeetCode547★★)/

 

2．11二叉排序樹和平衡二叉樹/

 

2．11．1二叉排序樹/

 

2．11．2平衡二叉樹/

 

2．11．3紅黑樹/

 

2．11．4Python中的有序類/

 

2．11．5實戰——前k個高頻單詞(LeetCode692★★)/

 

2．12哈希表/

 

2．12．1哈希表的基礎/

 

2．12．2Python中的哈希表/

 

2．12．3實戰——多數元素(LeetCode169★)/

 

習題2/

 

第3章必備技能——基本算法設計方法/

 

3．1窮舉法/

 

3．1．1窮舉法概述/

 

3．1．2最大連續子序列和/

 

3．1．3實戰——最大子序列和(LeetCode53★)/

 

3．2歸納法/

 

3．2．1歸納法概述/

 

3．2．2直接插入排序/

 

3．2．3實戰——不同路徑(LeetCode62★★)/

 

3．2．4猴子摘桃子問題/

 

3．3迭代法/

 

3．3．1迭代法概述/

 

3．3．2簡單選擇排序/

 

3．3．3實戰——多數元素(LeetCode169★)/

 

3．3．4求冪集/

 

3．3．5實戰——子集(LeetCode78★★)/

 

3．4遞歸法/

 

3．4．1遞歸法概述/

 

3．4．2冒泡排序/

 

3．4．3求全排列/

 

3．4．4實戰——字符串解碼(LeetCode394★★)/

 

3．5遞推式計算/

 

3．5．1直接展開法/

 

3．5．2遞歸樹方法/

 

3．5．3主方法/

 

習題3/

 

第4章分而治之——分治法/

 

4．1分治法概述/

 

4．1．1什麽是分治法/

 

4．1．2分治法算法的框架/

 

4．2求解排序問題/

 

4．2．1快速排序/

 

 

4．2．2實戰——最小的k個數(面試題17．14★★)/

 

4．2．3歸並排序/

 

4．2．4實戰——數組中的逆序對(劍指Offer51★★★)/

 

4．3求解查找問題/

 

4．3．1查找最大和次大元素/

 

4．3．2二分查找/

 

4．3．3二分查找的擴展/

 

4．3．4實戰——尋找峰值(LeetCode162★★)/

 

4．3．5查找兩個等長有序序列的中位數/

 

4．3．6查找假幣問題/

 

4．4求解組合問題/

 

4．4．1最大連續子序列的和/

 

4．4．2實戰——最大子序列的和(LeetCode53★)/

 

4．4．3實戰——多數元素(LeetCode169★)/

 

4．4．4實戰——三數之和(LeetCode15★★)/

 

4．4．5求最近點對距離/

 

習題4/

 

第5章走不下去就回退——回溯法/

 

5．1回溯法概述/

 

5．1．1問題的解空間/

 

5．1．2什麽是回溯法/

 

5．1．3回溯法算法的時間分析/

 

5．2深度優先搜索/

 

5．2．1圖的深度優先遍歷/

 

5．2．2深度優先遍歷和回溯法的差別/

 

5．2．3實戰——二叉樹的所有路徑(LeetCode257★)/

 

5．3基於子集樹框架的問題求解/

 

5．3．1子集樹算法框架概述/

 

5．3．2實戰——子集(LeetCode78★★)/

 

5．3．3實戰——子集Ⅱ(LeetCode90★★)/

 

5．3．4實戰——目標和(LeetCode494★★)/

 

5．3．5子集和問題/

 

5．3．6簡單裝載問題/

 

5．3．70/1背包問題/

 

5．3．8完全背包問題/

 

5．3．9實戰——皇後Ⅱ(LeetCode52★★★)/

 

5．3．10任務分配問題/

 

5．3．11*實戰——完成所有工作的最短時間

(LeetCode1723★★★)/

 

5．3．12圖的m著色/

 

5．4基於排列樹框架的問題求解/

 

5．4．1排列樹算法框架概述/

 

5．4．2實戰——含重復元素的全排列Ⅱ(LeetCode47★★)/

 

5．4．3任務分配問題/

 

5．4．4貨郎擔問題/

 

習題5/

 

第6章朝最優解方向前進——分支限界法/

 

6．1分支限界法概述/

 

6．1．1什麽是分支限界法/

 

6．1．2分支限界法的設計要點/

 

6．1．3分支限界法的時間分析/

 

6．2廣度優先搜索/

 

6．2．1圖的廣度優先遍歷/

 

6．2．2廣度優先搜索算法框架/

 

6．2．3實戰——到家的最少跳躍次數(LeetCode1654★★)/

 

6．2．4實戰——滑動謎題(LeetCode773★★★)/

 

6．2．5實戰——腐爛的橘子(LeetCode994★★)/

 

6．3隊列式分支限界法/

 

6．3．1隊列式分支限界法概述/

 

6．3．2圖的單源最短路徑/

 

6．3．3SPFA算法/

 

6．3．4實戰——網絡延遲時間(LeetCode743★★)/

 

6．3．50/1背包問題/

 

6．4優先隊列式分支限界法/

 

6．4．1優先隊列式分支限界法概述/

 

6．4．2圖的單源最短路徑/

 

6．4．3實戰——最小體力消耗路徑(LeetCode1631★★)/

 

6．4．4*實戰——完成所有工作的最短時間

(LeetCode1723★★★)/

 

6．4．50/1背包問題/

 

6．4．6任務分配問題/

 

6．4．7貨郎擔問題/

 

習題6/

 

第7章每一步局部最優——貪心法/

 

7．1貪心法概述/

 

7．1．1什麽是貪心法/

 

7．1．2貪心法求解問題具有的性質/

 

7．1．3實戰——分發餅乾(LeetCode455★)/

 

7．1．4貪心法的一般求解過程/

 

7．2求解組合問題/

 

7．2．1活動安排問題Ⅰ/

 

7．2．2實戰——無重疊區間(LeetCode435★★)/

 

7．2．3求解背包問題/

 

7．2．4實戰——雪糕的最大數量(LeetCode1833★★)/

 

7．2．5實戰——最大數(LeetCode179★★)/

 

7．2．6求解零錢兌換問題/

 

7．3求解圖問題/

 

7．3．1使用Prim算法構造最小生成樹/

 

7．3．2使用Kruskal算法構造最小生成樹/

 

7．3．3實戰——連接所有點的最小費用

(LeetCode1584★★)/

 

7．3．4使用Dijkstra算法求單源最短路徑/

 

7．3．5實戰——網絡延遲時間(LeetCode743★★)/

 

7．4求解調度問題/

 

7．4．1不帶懲罰的調度問題/

 

7．4．2帶懲罰的調度問題/

 

7．5哈夫曼編碼/

 

7．5．1哈夫曼樹和哈夫曼編碼/

 

7．5．2實戰——最後一塊石頭的重量

(LeetCode1046★)/

 

習題7/

 

第8章保存子問題的解——動態規劃/

 

8．1動態規劃概述/

 

8．1．1從一個簡單示例入門/

 

8．1．2動態規劃的原理/

 

8．1．3動態規劃求解問題的性質和步驟/

 

8．1．4動態規劃與其他方法的比較/

 

8．2一維動態規劃/

 

8．2．1最大連續子序列和/

 

8．2．2實戰——最大子序列和(LeetCode53★)/

 

8．2．3最長遞增子序列/

 

8．2．4*活動安排問題Ⅱ/

 

8．3二維動態規劃/

 

8．3．1三角形的最小路徑和/

 

8．3．2實戰——下降路徑最小和(LeetCode931★★)/

 

8．4三維動態規劃/

 

8．4．1使用Floyd算法求多源最短路徑/

 

8．4．2*雙機調度問題/

 

8．5字符串動態規劃/

 

8．5．1最長公共子序列/

 

8．5．2編輯距離/

 

8．6背包動態規劃/

 

8．6．10/1背包問題/

 

8．6．2實戰——目標和(LeetCode494★★)/

 

8．6．3完全背包問題/

 

8．6．4實戰——零錢兌換(LeetCode322★★)/

 

8．6．5*多重背包問題/

 

8．7樹形動態規劃/

 

8．7．1樹形動態規劃概述/

 

8．7．2實戰——找礦(LeetCode337★★)/

 

8．7．3實戰——監控二叉樹(LeetCode968★★★)/

 

8．8區間動態規劃/

 

8．8．1區間動態規劃概述/

 

8．8．2矩陣連乘問題/

 

8．8．3實戰——最長迴文子串(LeetCode5★★)/

 

習題8/

 

第9章最難問題——NP完全問題/

 

9．1P類和NP類/

 

9．1．1易解問題和難解問題/

 

9．1．2判定問題/

 

9．1．3P類/

 

9．1．4NP類/

 

9．2多項式時間變換和NP完全問題/

 

9．2．1多項式時間變換/

 

9．2．2NP完全性及其性質/

 

9．2．3第一個NP完全問題/

 

9．2．4其他NP完全問題/

 

習題9/

 

參考文獻/