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

本書系統地介紹了C++STL中各種數據結構容器的應用，討論窮舉法、歸納法、迭代法和遞歸法等基本算法設計方法，以及五大算法設計策略，即分治法、回溯法、分支限界法、貪心法和動態規劃的原理及典型算法設計，同時以LeetCode、POJ和HDU網站相關題目為實戰，深入剖析各種算法實現技術。 全書既註重原理又註重實踐，配有大量圖表、練習題、上機實驗題和在線編程題，內容豐富，概念講解清楚，表達嚴謹，邏輯性強，語言精練，可讀性強。 本書既便於教師課堂講授，又便於自學者閱讀，可作為高等院校“算法設計與分析”課程的教材，也可供ACM和各類程序設計競賽者參考。

目錄

掃一掃

源碼下載

第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二叉樹和優先隊列

2.4.1二叉樹

2.4.2優先隊列

2.4.3priority_queue優先隊列

容器

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最大連續子序列和

3.1.3字符串匹配

3.1.4實戰——查找單詞

(POJ1501)

3.2歸納法

3.2.1歸納法概述

3.2.2直接插入排序

3.2.3樓梯問題

3.2.4猴子摘桃子問題

3.2.5實戰——骨牌鋪方格

(HDU2046)

3.3迭代法

3.3.1迭代法概述

3.3.2簡單選擇排序

3.3.3求多數元素

3.3.4求冪集

3.3.5實戰——子集(LeetCode78)

3.4遞歸法

3.4.1遞歸法概述

3.4.2冒泡排序

3.4.3求全排列

3.4.4實戰——展開字符串

(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實戰——求逆序數

(POJ2299)

4.3求解查找問題

4.3.1查找最大和次大元素

4.3.2二分查找

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

中位數

4.3.4查找假幣問題

4.3.5*實戰——有序數組中的

單一元素(LeetCode540)

4.4求解組合問題

4.4.1最大連續子序列和

4.4.2棋盤覆蓋問題

4.4.3循環日程安排

問題

4.4.4求最近點對距離

4.4.5實戰——求兩組點之間的

最近點對(POJ3714)

4.5求xn和An問題

4.5.1求xn問題

4.5.2求An問題

4.5.3實戰——用矩陣快速冪求

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實戰——救援問題

(HDU1242)

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

5.3.1任務分配問題

5.3.2貨郎擔問題

5.3.3實戰——含重復元素的全

排列Ⅱ(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廣度優先搜索

6.2.1廣度優先搜索概述

6.2.2實戰——抓牛問題

(POJ3278)

6.2.3實戰——推箱子

(HDU1254)

6.2.4實戰——腐爛的橘子

(LeetCode994)

6.3隊列式分支限界法

6.3.1隊列式分支限界法概述

6.3.2圖的單源最短路徑

6.3.30/1背包問題

6.3.4實戰——網格中的最短

路徑(LeetCode1293)

6.4優先隊列式分支限界法

6.4.1優先隊列式分支限界法

概述

6.4.2圖的單源最短路徑

6.4.3實戰——最小體力消耗路

徑(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實戰——加工木棍

(POJ1065)

7.2.3求解背包問題

7.3求解圖問題

7.3.1用Prim算法構造最小生

成樹

7.3.2用Kruskal算法構造最小

生成樹

7.3.3實戰——建設道路

(POJ3625)

7.3.4用Dijkstra算法求單源

最短路徑

7.3.5實戰——最短路徑問題

(HDU3790)

7.4求解調度問題

7.4.1不帶懲罰的調度問題

7.4.2帶懲罰的調度問題

7.4.3實戰——趕作業

(HDU1789)

7.5哈夫曼編碼

7.5.1哈夫曼樹和哈夫曼編碼

7.5.2實戰——最後一塊石頭的

重量(LeetCode1046)

7.6練習題

7.6.1單項選擇題

7.6.2問答題

7.6.3算法設計題

7.7上機實驗題

7.8在線編程題

第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完全背包問題

8.6.3實戰——零錢兌換

(LeetCode322)

8.6.4*多重背包問題

8.7樹形動態規劃

8.7.1實戰——慶祝晚會

(HDU1520)

8.7.2實戰——找礦

(LeetCode337)

8.8區間動態規劃

8.8.1實戰——戳氣球

(LeetCode312)

8.8.2實戰——最長迴文

子串(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問答題

參考文獻