算法设计与分析基础（Java版）（微课视频版）

图书标准信息

• 作者 李春葆；刘娟；喻丹丹
• 出版社 清华大学出版社
• 出版时间 2023-10
• 版次 1
• ISBN 9787302625957
• 定价 59.80元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 362页
• 字数 0.58千字

【内容简介】

本书结合Java语言的数据结构（集合）介绍穷举法、归纳法、迭代法和递归法等基本算法设计方法，重点讨论分治法、回溯法、分支限界法、贪心法和动态规划五大算法设计策略的原理和算法设计框架，通过大量典型示例和LeetCode实战题解析了多途径构建模型、求解和算法实现的过程。 本书既注重原理又注重实践，配有大量图表、练习题、上机实验题和在线编程题，内容丰富、概念讲解清楚、表达严谨、逻辑性强、语言精练、可读性好。 本书既便于教师课堂讲授，又便于自学者阅读，适合作为高等院校“算法设计与分析”课程的教材，也可供ACM和各类程序设计竞赛者参考。

【作者简介】

:
李春葆，武汉大学计算机学院教授。主要研究方向为数据挖掘和算法设计，先后主持和参加多个大型研究项目。主要为本科生讲授数据结构（15年以上）和软件工程等课程，为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程，并出版十多部精品著作。

【目录】

第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