算法設計與分析基礎（C++版 微課視頻版）

第1章概論

1.1算法概述

1.1.1什么是算法

1.1.2算法描述

1.1.3算法和數據結構

1.1.4算法設計的基本步驟

1.2算法分析

1.2.1算法的時間復雜度分析

1.2.2算法的空間復雜度分析

1.3練習題

1.3.1單項選擇題

1.3.2問答題

1.3.3算法設計題

第2章常用數據結構及其應用

2.1線性表

2.1.1什么是線性表

2.1.2vector向量容器

2.1.3STL通用算法

2.1.4list鏈表容器

2.2字符串

2.2.1什么是字符串

2.2.2string字符串容器

2.3棧、隊列和雙端隊列

2.3.1什么是棧、隊列和雙端

隊列

2.3.2deque雙端隊列容器

2.3.3queue隊列容器

2.3.4stack棧容器

2.4二叉樹和優(yōu)先隊列

2.4.1二叉樹

2.4.2優(yōu)先隊列

2.4.3priority_queue優(yōu)先隊列

容器

2.5樹和并查集

2.5.1樹

2.5.2并查集

2.6圖

2.6.1圖基礎

2.6.2生成樹和最小生成樹

2.6.3最短路徑

2.6.4拓撲排序

2.7二叉排序樹和平衡二叉樹

2.7.1二叉排序樹

2.7.2平衡二叉樹

2.7.3集合容器set/multiset

2.7.4映射容器map/multimap

2.8哈希表

2.8.1什么是哈希表

2.8.2哈希集合容器unordered_set

2.8.3哈希映射容器unordered_map

2.9設計好的數據結構

2.10練習題

2.10.1單項選擇題

2.10.2問答題

2.10.3算法設計題

2.11上機實驗題

2.11.1高效地插入、刪除和

查找

2.11.2一種特殊的隊列

2.11.3方塊操作

2.12在線編程題

第3章基本算法設計方法

3.1窮舉法

3.1.1窮舉法概述

3.1.2最大連續(xù)子序列和

3.1.3字符串匹配

3.1.4實戰(zhàn)——查找單詞

(POJ1501)

3.2歸納法

3.2.1歸納法概述

3.2.2直接插入排序

3.2.3樓梯問題

3.2.4猴子摘桃子問題

3.2.5實戰(zhàn)——骨牌鋪方格

(HDU2046)

3.3迭代法

3.3.1迭代法概述

3.3.2簡單選擇排序

3.3.3求多數元素

3.3.4求冪集

3.3.5實戰(zhàn)——子集(LeetCode78)

3.4遞歸法

3.4.1遞歸法概述

3.4.2冒泡排序

3.4.3求全排列

3.4.4實戰(zhàn)——展開字符串

(HDU1274)

3.5遞推式計算

3.5.1直接展開法

3.5.2遞歸樹方法

3.5.3主方法

3.6練習題

3.6.1單項選擇題

3.6.2問答題

3.6.3算法設計題

3.7上機實驗題

3.8在線編程題

第4章分治法

4.1分治法概述

4.1.1什么是分治法

4.1.2分治法框架

4.2求解排序問題

4.2.1快速排序

4.2.2查找一個序列中第k小的

元素

4.2.3歸并排序

4.2.4實戰(zhàn)——求逆序數

(POJ2299)

4.3求解查找問題

4.3.1查找最大和次大元素

4.3.2二分查找

4.3.3查找兩個等長有序序列的

中位數

4.3.4查找假幣問題

4.3.5*實戰(zhàn)——有序數組中的

單一元素(LeetCode540)

4.4求解組合問題

4.4.1最大連續(xù)子序列和

4.4.2棋盤覆蓋問題

4.4.3循環(huán)日程安排

問題

4.4.4求最近點對距離

4.4.5實戰(zhàn)——求兩組點之間的

最近點對(POJ3714)

4.5求xn和An問題

4.5.1求xn問題

4.5.2求An問題

4.5.3實戰(zhàn)——用矩陣快速冪求

Fibonacci數列(POJ3070)

4.6練習題

4.6.1單項選擇題

4.6.2問答題

4.6.3算法設計題

4.7上機實驗題

4.8在線編程題

第5章回溯法

5.1回溯法概述

5.1.1問題的解空間

5.1.2什么是回溯法

5.1.3回溯法算法的框架

5.1.4回溯法算法的時間

分析

5.2基于子集樹框架的問題求解

5.2.1子集和問題

5.2.2簡單裝載問題

5.2.30/1背包問題

5.2.4n皇后問題

5.2.5任務分配問題

5.2.6出棧序列

5.2.7圖的m著色

5.2.8實戰(zhàn)——救援問題

(HDU1242)

5.3基于排列樹框架的問題求解

5.3.1任務分配問題

5.3.2貨郎擔問題

5.3.3實戰(zhàn)——含重復元素的全

排列Ⅱ(LeetCode47)

5.4練習題

5.4.1單項選擇題

5.4.2問答題

5.4.3算法設計題

5.5上機實驗題

5.6在線編程題

第6章分支限界法

6.1分支限界法概述

6.1.1什么是分支限界法

6.1.2分支限界法的設計要點

6.1.3分支限界法的時間分析

6.2廣度優(yōu)先搜索

6.2.1廣度優(yōu)先搜索概述

6.2.2實戰(zhàn)——抓牛問題

(POJ3278)

6.2.3實戰(zhàn)——推箱子

(HDU1254)

6.2.4實戰(zhàn)——腐爛的橘子

(LeetCode994)

6.3隊列式分支限界法

6.3.1隊列式分支限界法概述

6.3.2圖的單源最短路徑

6.3.30/1背包問題

6.3.4實戰(zhàn)——網格中的最短

路徑(LeetCode1293)

6.4優(yōu)先隊列式分支限界法

6.4.1優(yōu)先隊列式分支限界法

概述

6.4.2圖的單源最短路徑

6.4.3實戰(zhàn)——最小體力消耗路

徑(LeetCode1631)

6.4.40/1背包問題

6.4.5任務分配問題

6.4.6貨郎擔問題

6.5練習題

6.5.1單項選擇題

6.5.2問答題

6.5.3算法設計題

6.6上機實驗題

6.7在線編程題

第7章貪心法

7.1貪心法概述

7.1.1什么是貪心法

7.1.2貪心法求解問題具有的

性質

7.1.3貪心法的一般求解過程

7.2求解組合問題

7.2.1活動安排問題Ⅰ

7.2.2實戰(zhàn)——加工木棍

(POJ1065)

7.2.3求解背包問題

7.3求解圖問題

7.3.1用Prim算法構造最小生

成樹

7.3.2用Kruskal算法構造最小

生成樹

7.3.3實戰(zhàn)——建設道路

(POJ3625)

7.3.4用Dijkstra算法求單源

最短路徑

7.3.5實戰(zhàn)——最短路徑問題

(HDU3790)

7.4求解調度問題

7.4.1不帶懲罰的調度問題

7.4.2帶懲罰的調度問題

7.4.3實戰(zhàn)——趕作業(yè)

(HDU1789)

7.5哈夫曼編碼

7.5.1哈夫曼樹和哈夫曼編碼

7.5.2實戰(zhàn)——最后一塊石頭的

重量(LeetCode1046)

7.6練習題

7.6.1單項選擇題

7.6.2問答題

7.6.3算法設計題

7.7上機實驗題

7.8在線編程題

第8章動態(tài)規(guī)劃

8.1動態(tài)規(guī)劃概述

8.1.1從一個簡單示例入門

8.1.2動態(tài)規(guī)劃的原理

8.1.3動態(tài)規(guī)劃求解問題的性質

和步驟

8.1.4動態(tài)規(guī)劃與其他方法的

比較

8.2一維動態(tài)規(guī)劃

8.2.1最大連續(xù)子序列和

8.2.2實戰(zhàn)——最大子序列和

(LeetCode53)

8.2.3最長遞增子序列

8.2.4*活動安排問題Ⅱ

8.3二維動態(tài)規(guī)劃

8.3.1三角形最小路徑和

8.3.2實戰(zhàn)——下降路徑最小

和(LeetCode931)

8.4三維動態(tài)規(guī)劃

8.4.1用Floyd算法求多源最短

路徑

8.4.2*雙機調度問題

8.5字符串動態(tài)規(guī)劃

8.5.1最長公共子序列

8.5.2編輯距離

8.6背包動態(tài)規(guī)劃

8.6.10/1背包問題

8.6.2完全背包問題

8.6.3實戰(zhàn)——零錢兌換

(LeetCode322)

8.6.4*多重背包問題

8.7樹形動態(tài)規(guī)劃

8.7.1實戰(zhàn)——慶祝晚會

(HDU1520)

8.7.2實戰(zhàn)——找礦

(LeetCode337)

8.8區(qū)間動態(tài)規(guī)劃

8.8.1實戰(zhàn)——戳氣球

(LeetCode312)

8.8.2實戰(zhàn)——最長回文

子串(LeetCode5)

8.9練習題

8.9.1單項選擇題

8.9.2問答題

8.9.3算法設計題

8.10上機實驗題

8.11在線編程題

第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.3練習題

9.3.1單項選擇題

9.3.2問答題

參考文獻