目 录
1 题目分类 1
2 最易懂的贪心算法 3
2.1 算法解释 . . . . . . . . . . . . . 3
2.2 分配问题 . . . . . . . . . . . . . 3
2.3 区间问题 . . . . . . . . . . . . . 5
2.4 练习 . . . . . . . . . . . . . . . . 6
3 玩转双指针 8
3.1 算法解释 . . . . . . . . . . . . . 8
3.2 Two Sum . . . . . . . . . . . . . 9
3.3 归并两个有序数组 . . . . . . . . 10
3.4 快慢指针 . . . . . . . . . . . . . 10
3.5 滑动窗口 . . . . . . . . . . . . . 11
3.6 练习 . . . . . . . . . . . . . . . . 13
4 居合斩！二分查找 14
4.1 算法解释 . . . . . . . . . . . . . 14
4.2 求开方 . . . . . . . . . . . . . . 14
4.3 查找区间 . . . . . . . . . . . . . 15
4.4 旋转数组查找数字 . . . . . . . . 17
4.5 练习 . . . . . . . . . . . . . . . . 18
5 千奇百怪的排序算法 19
5.1 常用排序算法 . . . . . . . . . . 19
5.2 快速选择 . . . . . . . . . . . . . 21
5.3 桶排序 . . . . . . . . . . . . . . 22
5.4
练习
. . . . . . . . . . . . . . . . 23
6 一切皆可搜索 24
6.1 算法解释 . . . . . . . . . . . . . 24
6.2 深度优先搜索 . . . . . . . . . . 24
6.3 回溯法 . . . . . . . . . . . . . . 29
6.4 广度优先搜索 . . . . . . . . . . 34
6.5 练习 . . . . . . . . . . . . . . . . 38
7 深入浅出动态规划 40
7.1 算法解释 . . . . . . . . . . . . . 40
7.2 基本动态规划：一维 . . . . . . 40
7.3 基本动态规划：二维 . . . . . . 43
7.4 分割类型题 . . . . . . . . . . . . 47
7.5 子序列问题 . . . . . . . . . . . . 49
7.6 背包问题 . . . . . . . . . . . . . 51
7.7 字符串编辑 . . . . . . . . . . . . 57
7.8 股票交易 . . . . . . . . . . . . . 59
7.9 练习 . . . . . . . . . . . . . . . . 62
8 化繁为简的分治法 64
8.1 算法解释 . . . . . . . . . . . . . 64
8.2 表达式问题 . . . . . . . . . . . . 64
8.3 练习 . . . . . . . . . . . . . . . . 66
9 巧解数学问题 67
9.1 引言 . . . . . . . . . . . . . . . . 67
9.2 公倍数与公因数 . . . . . . . . . 67
9.3 质数 . . . . . . . . . . . . . . . . 67
9.4 数字处理 . . . . . . . . . . . . . 69
9.5 随机与取样 . . . . . . . . . . . . 71
9.6 练习 . . . . . . . . . . . . . . . . 74
10 神奇的位运算 76
10.1 常用技巧 . . . . . . . . . . . . . 76
10.2 位运算基础问题 . . . . . . . . . 76
10.3 二进制特性 . . . . . . . . . . . . 78
10.4 练习 . . . . . . . . . . . . . . . . 80
11 妙用数据结构 81
11.1 C++ STL . . . . . . . . . . . . . 81
11.2 数组 . . . . . . . . . . . . . . . . 82
11.3 栈和队列 . . . . . . . . . . . . . 85
11.4 单调栈 . . . . . . . . . . . . . . 88
11.5 优先队列 . . . . . . . . . . . . . 89
11.6 双端队列 . . . . . . . . . . . . . 93
11.7 哈希表 . . . . . . . . . . . . . . 94
11.8 多重集合和映射 . . . . . . . . . 98
11.9 前缀和与积分图 . . . . . . . . . 99
11.10练习 . . . . . . . . . . . . . . . . 102
