算法设计与分析基础（Java版）（微课视频版）_李春葆、刘娟、喻丹丹_9787302625957

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

党的二十大报告中指出：教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，这三大战略共同服务于创新型国家的建设。高等教育与经济社会发展紧密相连，对促进就业创业、助力经济社会发展、增进人民福祉具有重要意义。
用计算机求解问题是将特定问题的求解过程转换为计算机可以执行的程序，能够设计好的程序是计算机专业学生的基本功。在计算机教学体系中编程类的主要课程有高级程序设计语言数据结构算法设计与分析等，这些课程相互承接，程序设计语言是求解问题的工具，数据结构是求解问题的基础，算法设计是求解问题的关键。
算法设计与分析课程是计算机科学与技术等专业的必修课，旨在通过学习理解掌握算法设计的主要策略和算法复杂性分析的方法，并能熟练运用各种数据结构和常用算法策略设计高效算法，培养学生分析问题和解决复杂工程问题的能力，为学生进一步学习后续课程奠定良好的基础。本书是编者长期从事数据结构与算法设计与分析课程本科生和研究生教学中的经验总结，凝聚了编者的教学体会和理念。
1. 本书内容全书由9章构成，各章内容如下。
第1章算法入门概论：介绍算法的概念、算法描述方法、算法设计步骤和算法时空分析方法。
第2章工之利器常用数据结构及其应用：结合Java中的各种集合介绍线性表、字符串、栈、队列、双端队列、优先队列、树和二叉树、图、并查集、二叉排序树和平衡二叉树、哈希表等数据结构的原理和应用。
第3章技能基本算法设计方法：介绍穷举法、归纳法、迭代法和递归法等常用的算法设计方法，讨论递推式计算等基本算法分析方法。
第4章分而治之分治法：介绍分治法的原理和框架，讨论利用分治法求解排序问题、查找问题和组合问题等，包括快速排序、二路归并排序、二分查找、假币问题、最大连续子序列和、多数元素和最近点对距离等典型算法。
第5章走不下去就回退回溯法：介绍解空间的概念和回溯法的框架，根据解空间的类型分别讨论基于子集树框架的问题求解和基于排列树框架的问题求解方法，包括子集和问题、简单装载问题、0/1背包问题、n皇后问题、任务分配问题、图的m着色和货郎担问题等典型算法。
第6章朝最优解方向前进分支限界法：介绍分支限界法的要点和框架，讨论广度优先搜索、队列式分支限界法和优先队列式分支限界法，包括图的单源最短路径、0/1背包问题、任务分配问题和货郎担问题等典型算法。
第7章每一步都局部最优贪心法：介绍贪心法的策略和要点，讨论采用贪心法求解组合问题、图问题、调度问题和哈夫曼编码，包括活动安排问题Ⅰ、Prim、Kruskal、Dijkstra和不带/带惩罚的调度问题等典型算法。
第8章保存子问题的解动态规划：介绍动态规划的原理和要点，讨论一维动态规划、二维动态规划、三维动态规划、字符串动态规划、背包动态规划、树形动态规划和区间动态规划算法设计方法，包括最大连续子序列和、最长递增子序列、活动安排问题Ⅱ、三角形最小路径和、Floyd算法、双机调度问题、最长公共子序列、编辑距离、0/1背包问题、完全背包问题和多重背包问题等典型算法。
第9章最难问题NP完全问题：介绍P类、NP类和NP完全问题。
书中带的部分作为选学内容。
2. 本书特色本书具有如下鲜明特色：
（1）由浅入深，循序渐进。每种算法策略从设计思想、算法框架入手，由易到难地讲解经典问题的求解过程，使读者既能学到求解问题的方法，又能通过对算法策略的反复应用掌握其核心原理，以收到融会贯通之效。
（2）示例丰富，重视启发。书中列举大量的具有典型性的求解问题，深入剖析采用相关算法策略求解的思路，展示算法设计的清晰过程，并举一反三，激发学生学习算法设计的兴趣。
（3）注重求解问题的多维性。同一个问题采用多种算法策略实现，例如0/1背包问题采用回溯法、分支限界法和动态规划求解等。通过不同算法策略的比较，使读者更容易体会每一种算法策略的设计特点和各自的优缺点，以提高算法设计的效率。
（4）强调实践和动手能力的培养。书中针对相关知识点以实战题形式讨论了LeetCode（力扣）网站部分在线编程题的设计思路和解决过程，让学生体会学以致用和解决实际问题的乐趣。实战题按难度分为3个级别，即★、★★和★★★，分别对应简单、中等和困难。
（5）本书配套有《算法设计与分析基础（Java版）学习与上机实验指导》（李春葆等，清华大学出版社，2023），涵盖所有练习题、上机实验题和在线编程题的参考答案。
3. 教学资源为了方便教师教学和学生学习，本书提供全面而丰富的教学资源，包括的内容如下。
（1）教学PPT：提供全部教学内容的精美PPT课件，供任课教师在教学中使用。
（2）源程序代码：所有源代码按章组织，例如ch3文件夹存放第3章的源代码，其中perm.java为求全排列的源代码。
（3）算法设计与分析课程教学大纲和电子教案：包含教学目的、课程内容和学时分配（44学时），以及各章的课程思政要点、每个课时的教学内容安排。
（4）算法设计与分析实验课程教学大纲：包含课程介绍、教学目的、实验基本要求与方式、实验报告、实验内容与学时分配（15～21学时），以及推荐的在线编程题题目。
（5）微课视频：包含99个视频，总时长18小时。
资源下载提示
素材（源码）等资源：扫描目录上方的二维码下载。
微课视频：扫描封底的文泉云盘防盗码，再扫描书中相应章节的视频讲解二维码，可以在线学习。

本书的出版得到武汉大学计算机学院核心课程建设项目的资助和清华大学出版社魏江江分社长的全力支持，王冰飞老师给予精心编辑，力扣网站提供了无私的帮助，编者在此一并表示衷心感谢。尽管编者不遗余力，但由于水平所限，本书仍存在不足之处，敬请教师和同学们批评指正。

编者
2023年7月

第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

我要评论