算法设计与分析基础(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问答题
参考文献