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

　　本书系统地介绍了C++STL中各种数据结构容器的应用，讨论穷举法、归纳法、迭代法和递归法等基本算法设计方法，以及五大算法设计策略，即分治法、回溯法、分支限界法、贪心法和动态规划的原理及典型算法设计，同时以LeetCode、POJ和HDU网站相关题目为实战，深入剖析各种算法实现技术。全书既注重原理又注重实践，配有大量图表、练习题、上机实验题和在线编程题，内容丰富，概念讲解清楚，表达严谨，逻辑性强，语言精练，可读性强。本书既便于教师课堂讲授，又便于自学者阅读，可作为高等院校“算法设计与分析”课程的教材，也可供ACM和各类程序设计竞赛者参考。

　　李春葆，武汉大学教授，主要研究方向为数据挖掘和算法设计，从事近30年C/C++语言、数据结构和算法设计等课程的第一线本科教学工作，具备丰富的教学经验，曾参与深圳名企的笔试和面试题库建设。出版多本C/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二叉树和优先队列

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问答题

参考文献