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

本書結合Java語言的數據結構（集合）介紹窮舉法、歸納法、迭代法和遞歸法等基本算法設計方法，重點討論分治法、回溯法、分支限界法、貪心法和動態規劃五大算法設計策略的原理和算法設計框架，通過大量典型示例和LeetCode實戰題解析了多途徑構建模型、求解和算法實現的過程。 本書既註重原理又註重實踐，配有大量圖表、練習題、上機實驗題和在線編程題，內容豐富、概念講解清楚、表達嚴謹、邏輯性強、語言精練、可讀性好。 本書既便於教師課堂講授，又便於自學者閱讀，適合作為高等院校“算法設計與分析”課程的教材，也可供ACM和各類程序設計競賽者參考。

目錄

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

11算法概述/2

1.1.1什麽是算法/2

1.1.2算法描述/3

1.1.3算法設計的基本步驟/5

12算法分析/5

1.2.1算法的時間復雜度分析/6

1.2.2算法的空間復雜度分析/14

13練習題/14

1.3.1單項選擇題/14

1.3.2問答題/16

1.3.3算法設計題/18

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

21線性表——數組/20

2.1.1線性表的定義/20

2.1.2Java數組/20

2.1.3實戰——移除元素（LeetCode27★）/20

2.1.4Arrays類及其應用/22

2.1.5ArrayList類及其應用/26

22線性表——鏈表/29

2.2.1單鏈表/29

2.2.2實戰——反轉鏈表（LeetCode206★）/30

2.2.3LinkedList類/31

23字符串/31

2.3.1字符串的定義/31

2.3.2String類/31

2.3.3實戰——最大重復子字符串（LeetCode1668★）/33

24棧/33

2.4.1棧的定義/33

2.4.2Stack棧類/34

2.4.3實戰——使括號有效的最少添加（LeetCode921★★）/34

25隊列/35

2.5.1隊列的定義/35

2.5.2Queue隊列接口/35

2.5.3實戰——無法吃午餐的學生數量（LeetCode1700★）/36

26雙端隊列/37

2.6.1雙端隊列的定義/37

2.6.2Deque雙端隊列接口/38

2.6.3實戰——滑動窗口中的最大值（LeetCode239★★★）/38

27優先隊列/40

2.7.1優先隊列的定義/40

2.7.2PriorityQueue優先隊列類/40

2.7.3實戰——滑動窗口中的最大值（LeetCode239★★★）/42

28樹和二叉樹/43

2.8.1樹/43

2.8.2二叉樹/43

2.8.3實戰——二叉樹的完全性檢驗（LeetCode958★★）/45

29圖/46

2.9.1圖基礎/46

2.9.2實戰——課程表（LeetCode207★★）/49

210並查集/50

2.10.1並查集基礎/50

2.10.2實戰——省份數量（LeetCode547★★）/53

211二叉排序樹和平衡二叉樹/54

2.11.1二叉排序樹/54

2.11.2平衡二叉樹/55

2.11.3紅黑樹/55

2.11.4TreeMap類和TreeSet類/55

2.11.5實戰——前k個高頻單詞（LeetCode692★★）/57

212哈希表/59

2.12.1哈希表基礎/59

2.12.2HashMap類和HashSet類/59

2.12.3實戰——多數元素（LeetCode169★）/62

213練習題/63

2.13.1單項選擇題/63

2.13.2問答題/64

2.13.3算法設計題/66

在線編程題/67

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

31窮舉法/70

3.1.1窮舉法概述/70

3.1.2最大連續子序列和/72

3.1.3實戰——最大子序列和（LeetCode53★）/76

32歸納法/77

3.2.1歸納法概述/77

3.2.2直接插入排序/79

3.2.3實戰——不同路徑（LeetCode62★★）/80

3.2.4猴子摘桃子問題/81

33迭代法/82

3.3.1迭代法概述/82

3.3.2簡單選擇排序/83

3.3.3實戰——多數元素（LeetCode169★）/84

3.3.4求冪集/85

3.3.5實戰——子集（LeetCode78★★）/87

34遞歸法/88

3.4.1遞歸法概述/88

3.4.2冒泡排序/91

3.4.3求全排列/93

3.4.4實戰——字符串解碼（LeetCode394★★）/95

35遞推式計算/96

3.5.1直接展開法/96

3.5.2遞歸樹方法/97

3.5.3主方法/99

36練習題/100

3.6.1單項選擇題/100

3.6.2問答題/102

3.6.3算法設計題/104

在線編程題/104

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

41分治法概述/108

4.1.1什麽是分治法/108

4.1.2分治法框架/108

42求解排序問題/110

4.2.1快速排序/110

4.2.2實戰——最小的k個數（面試題17.14★★）/113

4.2.3歸並排序/115

4.2.4實戰——數組中的逆序對（劍指Offer51★★★）/117

43求解查找問題/119

4.3.1查找最大和次大元素/119

4.3.2二分查找/120

4.3.3二分查找的擴展/123

4.3.4實戰——尋找峰值（LeetCode162★★）/124

4.3.5查找兩個等長有序序列的中位數/125

4.3.6查找假幣問題/127

44求解組合問題/130

4.4.1最大連續子序列和/130

4.4.2實戰——最大子序列和（LeetCode53★）/133

4.4.3實戰——多數元素（LeetCode169★）/134

4.4.4實戰——三數之和（LeetCode15★★）/135

4.4.5求最近點對距離/137

4.4.6實戰——求兩組點之間的最近點對（POJ3714）/139

45練習題/142

4.5.1單項選擇題/142

4.5.2問答題/143

4.5.3算法設計題/144

在線編程題/145

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

51回溯法概述/148

5.1.1問題的解空間/148

5.1.2什麽是回溯法/149

5.1.3回溯法算法的時間分析/151

52深度優先搜索/151

5.2.1圖的深度優先遍歷/151

5.2.2深度優先遍歷和回溯法的差別/152

5.2.3實戰——二叉樹的所有路徑（LeetCode257★）/153

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

5.3.1子集樹算法框架概述/156

5.3.2實戰——子集（LeetCode78★★）/156

5.3.3實戰——子集Ⅱ（LeetCode90★★）/158

5.3.4實戰——目標和（LeetCode494★★）/159

5.3.5子集和問題/160

5.3.6簡單裝載問題/165

5.3.70/1背包問題/168

5.3.8完全背包問題/172

5.3.9實戰——皇後Ⅱ（LeetCode52★★★）/174

5.3.10任務分配問題/176

5.3.11實戰——完成所有工作的最短時間（LeetCode1723★★★）/179

5.3.12圖的m著色/183

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

5.4.1排列樹算法框架概述/184

5.4.2實戰——含重復元素的全排列Ⅱ（LeetCode47★★）/187

5.4.3任務分配問題/189

5.4.4貨郎擔問題/192

55練習題/194

5.5.1單項選擇題/194

5.5.2問答題/195

5.5.3算法設計題/198

在線編程題/199

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

61分支限界法概述/202

6.1.1什麽是分支限界法/202

6.1.2分支限界法的設計要點/202

6.1.3分支限界法的時間分析/204

62廣度優先搜索/204

6.2.1圖的廣度優先遍歷/204

6.2.2廣度優先搜索算法框架/205

6.2.3實戰——到家的最少跳躍次數（LeetCode1654★★）/207

6.2.4實戰——滑動謎題（LeetCode773★★★）/208

6.2.5實戰——腐爛的橘子（LeetCode994★★）/210

63隊列式分支限界法/212

6.3.1隊列式分支限界法概述/212

6.3.2圖的單源最短路徑/213

6.3.3SPFA算法/217

6.3.4實戰——網絡延遲時間（LeetCode743★★）/219

6.3.50/1背包問題/222

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

6.4.1優先隊列式分支限界法概述/226

6.4.2圖的單源最短路徑/226

6.4.3實戰——最小體力消耗路徑（LeetCode1631★★）/229

6.4.4實戰——完成所有工作的最短時間（LeetCode1723★★★）/231

6.4.50/1背包問題/233

6.4.6任務分配問題/236

6.4.7貨郎擔問題/239

65練習題/242

6.5.1單項選擇題/242

6.5.2問答題/243

6.5.3算法設計題/244

在線編程題/245

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

71貪心法概述/248

7.1.1什麽是貪心法/248

7.1.2貪心法求解問題具有的性質/248

7.1.3實戰——分發餅乾（LeetCode455★）/249

7.1.4貪心法的一般求解過程/250

72求解組合問題/251

7.2.1活動安排問題Ⅰ /251

7.2.2實戰——無重疊區間（LeetCode435★★）/254

7.2.3求解背包問題/256

7.2.4實戰——雪糕的最大數量（LeetCode1833★★）/259

7.2.5實戰——最大數（LeetCode179★★）/260

7.2.6求解零錢兌換問題/261

73求解圖問題/262

7.3.1用Prim算法構造最小生成樹/262

7.3.2用Kruskal算法構造最小生成樹/265

7.3.3實戰——連接所有點的最小費用（LeetCode1584★★）/267

7.3.4用Dijkstra算法求單源最短路徑/271

7.3.5實戰——網絡延遲時間（LeetCode743★★）/274

74求解調度問題/275

7.4.1不帶懲罰的調度問題/275

7.4.2帶懲罰的調度問題/277

75哈夫曼編碼/279

7.5.1哈夫曼樹和哈夫曼編碼/279

7.5.2實戰——最後一塊石頭的重量（LeetCode1046★）/283

76練習題/284

7.6.1單項選擇題/284

7.6.2問答題/286

7.6.3算法設計題/286

在線編程題/287

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

81動態規劃概述/290

8.1.1從一個簡單示例入門/290

8.1.2動態規劃的原理/293

8.1.3用動態規劃求解問題的性質和步驟/296

8.1.4動態規劃與其他方法的比較/297

82一維動態規劃/297

8.2.1最大連續子序列和/298

8.2.2實戰——最大子序列和（LeetCode53★）/300

8.2.3最長遞增子序列/301

8.2.4活動安排問題Ⅱ/303

83二維動態規劃/306

8.3.1三角形最小路徑和/306

8.3.2實戰——下降路徑最小和（LeetCode931★★）/310

84三維動態規劃/315

8.4.1用Floyd算法求多源最短路徑/315

8.4.2雙機調度問題/316

85字符串動態規劃/320

8.5.1最長公共子序列/320

8.5.2編輯距離/324

86背包動態規劃/325

8.6.10/1背包問題/325

8.6.2實戰——目標和（LeetCode494★★）/329

8.6.3完全背包問題/331

8.6.4實戰——零錢兌換（LeetCode322★★）/334

8.6.5多重背包問題/335

87樹形動態規劃/336

8.7.1樹形動態規劃概述/336

8.7.2實戰——找礦（LeetCode337★★）/337

8.7.3實戰——監控二叉樹（LeetCode968★★★）/339

88區間動態規劃/341

8.8.1區間動態規劃概述/341

8.8.2矩陣連乘問題/342

8.8.3實戰——最長迴文子串（LeetCode5★★）/344

89練習題/346

8.9.1單項選擇題/346

8.9.2問答題/348

8.9.3算法設計題/348

在線編程題/350

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

91P類和NP類/354

9.1.1易解問題和難解問題/354

9.1.2判定問題/354

9.1.3P類/355

9.1.4NP類/355

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

9.2.1多項式時間變換/357

9.2.2NP完全問題及其性質/358

9.2.3第一個NP完全問題/358

9.2.4其他NP完全問題/359

93練習題/361

9.3.1單項選擇題/361

9.3.2問答題/362

參考文獻/363