算法设计与分析基础(Python语言描述微课视频版题库版高等学校算法类课程系列教材)

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

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

第1章 算法入门——概论 1.1 算法概述 1.1.1 什么是算法 1.1.2 算法的描述 1.1.3 算法设计的基本步骤 1.2 算法分析 1.2.1 算法的时间复杂度分析 1.2.2 算法的空间复杂度分析 习题1 第2章 工之利器——常用数据结构及其应用 2.1 线性表——数组 2.1.1 线性表的定义 2.1.2 Python列表 2.1.3 列表元素的排序 2.1.4 列表的复制 2.1.5 实战——移除元素(LeetCode27★) 2.2 线性表——链表 2.2.1 单链表 2.2.2 实战——反转链表(LeetCode206★) 2.3 字符串 2.3.1 字符串的定义 2.3.2 Python中的字符串 2.3.3 实战——最大重复子字符串(LeetCode1668★) 2.4 栈 2.4.1 栈的定义 2.4.2 用Python列表实现栈 2.4.3 实战——使括号有效的最少添加(LeetCode921★★) 2.5 双端队列 2.5.1 双端队列的定义 2.5.2 Python中的双端队列 2.5.3 实战——滑动窗口中的最大值(LeetCode239★★★) 2.6 队列 2.6.1 队列的定义 2.6.2 Python中的队列 2.6.3 实战——无法吃午餐的学生的数量(LeetCode1700★) 2.7 优先队列 2.7.1 优先队列的定义 2.7.2 Python中的优先队列 2.7.3 实战——数据流中第k大的元素(LeetCode703★) 2.8 树和二叉树 2.8.1 树 2.8.2 二叉树 2.8.3 实战——二叉树的完全性检验(LeetCode958★★) 2.9 图 2.9.1 图的基础 2.9.2 实战——课程表(LeetCode207★★) 2.10 并查集 2.10.1 并查集的基础 2.10.2 实战——省份的数量(LeetCode547★★) 2.11 二叉排序树和平衡二叉树 2.11.1 二叉排序树 2.11.2 平衡二叉树 2.11.3 红黑树 2.11.4 Python中的有序类 2.11.5 实战——前k个高频单词(LeetCode692★★) 2.12 哈希表 2.12.1 哈希表的基础 2.12.2 Python中的哈希表 2.12.3 实战——多数元素(LeetCode169★) 习题2 第3章 必备技能——基本算法设计方法 3.1 穷举法 3.1.1 穷举法概述 3.1.2 最大连续子序列和 3.1.3 实战——最大子序列和(LeetCode53★) 3.2 归纳法 3.2.1 归纳法概述 3.2.2 直接插入排序 3.2.3 实战——不同路径(LeetCode62★★) 3.2.4 猴子摘桃子问题 3.3 迭代法 3.3.1 迭代法概述 3.3.2 简单选择排序 3.3.3 实战——多数元素(LeetCode169★) 3.3.4 求幂集 3.3.5 实战——子集(LeetCode78★★) 3.4 递归法 3.4.1 递归法概述 3.4.2 冒泡排序 3.4.3 求全排列 3.4.4 实战——字符串解码(LeetCode394★★) 3.5 递推式计算 3.5.1 直接展开法 3.5.2 递归树方法 3.5.3 主方法 习题3 第4章 分而治之——分治法 4.1 分治法概述 4.1.1 什么是分治法 4.1.2 分治法算法的框架 4.2 求解排序问题 4.2.1 快速排序 4.2.2 实战——最小的k个数(面试题17.14★★) 4.2.3 归并排序 4.2.4 实战——数组中的逆序对(剑指Offer51★★★) 4.3 求解查找问题 4.3.1 查找最大和次大元素 4.3.2 二分查找 4.3.3 二分查找的扩展 4.3.4 实战——寻找峰值(LeetCode162★★) 4.3.5 查找两个等长有序序列的中位数 4.3.6 查找假币问题 4.4 求解组合问题 4.4.1 最大连续子序列的和 4.4.2 实战——最大子序列的和(LeetCode53★) 4.4.3 实战——多数元素(LeetCode169★) 4.4.4 实战——三数之和(LeetCode15★★) 4.4.5 求最近点对距离 习题4 第5章 走不下去就回退——回溯法 5.1 回溯法概述 5.1.1 问题的解空间 5.1.2 什么是回溯法 5.1.3 回溯法算法的时间分析 5.2 深度优先搜索 5.2.1 图的深度优先遍历 5.2.2 深度优先遍历和回溯法的差别 5.2.3 实战——二叉树的所有路径(LeetCode257★) 5.3 基于子集树框架的问题求解 5.3.1 子集树算法框架概述 5.3.2 实战——子集(LeetCode78★★) 5.3.3 实战——子集Ⅱ(LeetCode90★★) 5.3.4 实战——目标和(LeetCode494★★) 5.3.5 子集和问题 5.3.6 简单装载问题 5.3.7 0/1背包问题 5.3.8 完全背包问题 5.3.9 实战——皇后Ⅱ(LeetCode52★★★) 5.3.10 任务分配问题 5.3.11 *实战——完成所有工作的最短时间(LeetCode1723★★★) 5.3.12 图的m着色 5.4 基于排列树框架的问题求解 5.4.1 排列树算法框架概述 5.4.2 实战——含重复元素的全排列Ⅱ(LeetCode47★★) 5.4.3 任务分配问题 5.4.4 货郎担问题 习题5 第6章