数据之美

内容简介

本书结合实际应用场景讲解数据结构和算法,涵盖常用、常考的数据结构和算法的原理讲解、代码实现和应用场景等。

本书分为11章。
第1章介绍复杂度分析方法。
第2章介绍数组、链表、栈和队列这些基础的线性表数据结构。
第3章介绍递归编程技巧、8种经典排序、二分查找及二分查找的变体问题。
第4章介绍哈希表、位图、哈希算法和布隆过滤器。
第5章介绍树相关的数据结构,包括二叉树、二叉查找树、平衡二叉查找树、递归树和B+树。
第6章介绍堆,以及堆的各种应用,包括堆排序、优先级队列、求Top K、求中位数和求百分位数。
第7章介绍跳表、并查集、线段树和树状数组这些比较高级的数据结构。
第8章介绍字符串匹配算法,包括BF算法、RK算法、BM算法、KMP算法、Trie树和AC自动机。
第9章介绍图及相关算法,包括深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、Floyd算法、A*算法、最小生成树算法、最大流算法和最大二分匹配等。
第10章介绍4种算法思想,包括贪心、分治、回溯和动态规划。
第11章介绍4个经典项目中的数据结构和算法的应用,包括Redis、搜索引擎、鉴权限流和短网址服务。
另外,附录A为书中的思考题的解答。

尽管本书的大部分代码采用Java语言编写,但本书讲解的知识与具体编程语言无关,因此,本书不但适合各种类型的研发工程师,而且可以作为高校计算机相关专业师生的学习用书和培训学校的教材。

作者简介

王争,前Google工程师,微信公众号【小争哥】作者,GitHub上算法教程Star数排名前列。
热衷分享,致力于通俗易懂地讲解数据结构和算法,帮助广大程序员攻克算法学习、算法刷题、算法面试三项难关。

目录

第1章复杂度分析 1
1.1复杂度分析(上):如何分析代码的执行效率和资源消耗 2
1.1.1复杂度分析的意义 2
1.1.2大O复杂度表示法 2
1.1.3时间复杂度分析方法 4
1.1.4几种常见的时间复杂度量级 5
1.1.5空间复杂度分析方法 7
1.1.6内容小结 7
1.1.7思考题 8
1.2复杂度分析(下):详解最好、最坏、平均、均摊这4种时间复杂度 8
1.2.1最好时间复杂度和最坏时间复杂度 8
1.2.2平均时间复杂度 9
1.2.3均摊时间复杂度 10
1.2.4内容小结 11
1.2.5思考题 12
第2章数组、链表、栈和队列 13
2.1数组(上):为什么数组的下标一般从0开始编号 14
2.1.1数组的定义 14
2.1.2寻址公式和随机访问特性 15
2.1.3低效的插入和删除操作 15
2.1.4警惕数组访问越界问题 16
2.1.5容器能否完全替代数组 17
2.1.6解答本节开篇问题 18
2.1.7内容小结 18
2.1.8思考题 18
2.2数组(下):数据结构中的数组和编程语言中的数组的区别 19
2.2.1C/C++中数组的实现方式 19
2.2.2Java中数组的实现方式 20
2.2.3JavaScript中数组的实现方式 22
2.2.4内容小结 23
2.2.5思考题 23
2.3链表(上):如何基于链表实现LRU缓存淘汰算法 23
2.3.1链表的底层存储结构 24
2.3.2链表的定义和操作 24
2.3.3链表的变形结构 26
2.3.4链表与数组的性能对比 28
2.3.5解答本节开篇问题 29
2.3.6内容小结 29
2.3.7思考题 30
2.4链表(下):借助哪些技巧可以轻松地编写链表相关的复杂代码 30
2.4.1技巧1:理解指针或引用的含义 30
2.4.2技巧2:警惕指针丢失和内存泄露 30
2.4.3技巧3:利用“哨兵”简化代码 31
2.4.4技巧4:留意边界条件和特殊情况 33
2.4.5技巧5:举例画图,辅助思考 34
2.4.6技巧6:多写多练,没有捷径 34
2.4.7内容小结 34
2.4.8思考题 35
2.5栈:如何实现浏览器的前进和后退功能 35
2.5.1栈的定义 35
2.5.2顺序栈和链式栈 35
2.5.3支持动态扩容的顺序栈 36
2.5.4栈在函数调用中的应用 37
2.5.5栈在表达式求值中的应用 38
2.5.6栈在括号匹配中的应用 38
2.5.7解答本节开篇问题 39
2.5.8内容小结 40
2.5.9思考题 40
2.6队列:如何实现线程池等有限资源池的请求排队功能 40
2.6.1队列的定义 40
2.6.2顺序队列和链式队列 41
2.6.3循环队列 42
2.6.4阻塞队列和并发队列 44
2.6.5解答本节开篇问题 44
2.6.6内容小结 45
2.6.7思考题 45
第3章递归、排序、二分查找 46
3.1递归:如何用3行代码找到“最终推荐人” 47
3.1.1什么是递归 47
3.1.2递归需要满足的3个条件 48
3.1.3如何编写递归代码 48
3.1.4编写递归代码的难点 49
3.1.5警惕递归代码出现堆栈溢出 49
3.1.6警惕递归代码的重复计算问题 50
3.1.7将递归代码改写为非递归代码 51
3.1.8解答本节开篇问题 52
3.1.9内容小结 52
3.1.10思考题 52
3.2尾递归:如何借助尾递归避免递归过深导致的堆栈溢出 53
3.2.1递归产生堆栈溢出的原因 53
3.2.2什么样的递归代码可以改写为尾递归 54
3.2.3尾递归真的可以避免堆栈溢出吗 54
3.2.4思考题 55
3.3排序算法基础:从哪几个方面分析排序算法 55
3.3.1排序算法的执行效率 55
3.3.2排序算法的内存消耗 56
3.3.3排序算法的稳定性 56
3.3.4内容小结 57
3.3.5思考题 57
3.4O(n2)排序:为什么插入排序比冒泡排序更受欢迎 58
3.4.1冒泡排序 58
3.4.2插入排序 60
3.4.3选择排序 62
3.4.4解答本节开篇问题 63
3.4.5内容小结 64
3.4.6思考题 64
3.5O(nlogn)排序:如何借助快速排序思想快速查找第K大元素 64
3.5.1归并排序的原理和实现 64
3.5.2归并排序的性能分析 66
3.5.3快速排序的原理和实现 68
3.5.4快速排序的性能分析 70
3.5.5解答本节开篇问题 71
3.5.6内容小结 72
3.5.7思考题 72
3.6线性排序:如何根据年龄给100万个用户排序 72
3.6.1桶排序 73
3.6.2计数排序 74
3.6.3基数排序 76
3.6.4解答本节开篇问题 77
3.6.5内容小结 77
3.6.6思考题 77
3.7排序优化:如何实现一个高性能的通用的排序函数 78
3.7.1如何选择合适的排序算法 78
3.7.2如何优化快速排序 79
3.7.3排序函数举例分析 79
3.7.4内容小结 80
3.7.5思考题 80
3.8二分查找:如何用最省内存的方式实现快速查找功能 80
3.8.1无处不在的二分思想 81
3.8.2O(logn)惊人的查找速度 82
3.8.3二分查找的递归与非递归实现 82
3.8.4二分查找应用场景的局限性 83
3.8.5解答本节开篇问题 84
3.8.6内容小结 85
3.8.7思考题 85
3.9二分查找的变体:如何快速定位IP地址对应的归属地 85
3.9.1什么是二分查找变体问题 86
3.9.2变体问题1:查找第一个值等于给定值的元素 86
3.9.3变体问题2:查找最后一个值等于给定值的元素 88
3.9.4变体问题3:查找第一个值大于或等于给定值的元素 88
3.9.5变体问题4:查找最后一个值小于或等于给定值的元素 89
3.9.6解答本节开篇问题 89
3.9.7内容小结 90
3.9.8思考题 90
第4章哈希表、位图和哈希算法 91
4.1哈希表(上):Word软件的单词拼写检查功能是如何实现的 92
4.1.1哈希思想 92
4.1.2哈希函数 93
4.1.3哈希冲突 93
4.1.4解答本节开篇问题 95
4.1.5内容小结 95
4.1.6思考题 96
4.2哈希表(中):如何打造一个工业级的哈希表 96
4.2.1设计哈希函数 96
4.2.2解决装载因子过大的问题 97
4.2.3避免低效的扩容 98
4.2.4选择合适的冲突解决方法 99
4.2.5工业级的哈希表举例分析 100
4.2.6解答本节开篇问题 100
4.2.7内容小结 101
4.2.8思考题 101
4.3哈希表(下):如何利用哈希表优化LRU缓存淘汰算法 101
4.3.1LRU缓存淘汰算法 102
4.3.2Java LinkedHashMap 104
4.3.3内容小结 105
4.3.4思考题 105
4.4位图:如何实现网页“爬虫”中的网址链接去重功能 106
4.4.1基于哈希表的解决方案 106
4.4.2基于位图的解决方案 106
4.4.3基于布隆过滤器的解决方案 108
4.4.4回答本节开篇问题 110
4.4.5内容小结 110
4.4.6思考题 111
4.5哈希算法:如何防止数据库脱库后用户信息泄露 111
4.5.1哈希算法介绍 111
4.5.2应用1:安全加密 112
4.5.3应用2:唯一标识 113
4.5.4应用3:数据校验 113
4.5.5应用4:哈希函数 113
4.5.6应用5:负载均衡 114
4.5.7应用6:数据分片 114
4.5.8应用7:分布式存储 115
4.5.9解答本节开篇问题 116
4.5.10内容小结 116
4.5.11思考题 116
第5章树 117
5.1树和二叉树:什么样的二叉树适合用数组存储 118
5.1.1树的定义 118
5.1.2二叉树的定义 118
5.1.3二叉树的存储 119
5.1.4二叉树的遍历 120
5.1.5解答本节开篇问题 122
5.1.6内容小结 122
5.1.7思考题 122
5.2二叉查找树:相比哈希表,二叉查找树有何优势 122
5.2.1二叉查找树的定义和操作 123
5.2.2支持重复数据的二叉查找树 126
5.2.3二叉查找树的性能分析 126
5.2.4解答本节开篇问题 127
5.2.5内容小结 128
5.2.6思考题 128
5.3平衡二叉查找树:为什么红黑树如此受欢迎 128
5.3.1平衡二叉查找树的定义 128
5.3.2红黑树的定义 129
5.3.3红黑树的性能分析 129
5.3.4解答本节开篇问题 130
5.3.5内容小结 130
5.3.6思考题 131
5.4递归树:如何借助树求递归算法的时间复杂度 131
5.4.1递归树时间复杂度分析法 131
5.4.2实战1:快速排序的时间复杂度分析 132
5.4.3实战2:斐波那契数列的时间复杂度分析 133
5.4.4实战3:全排列的时间复杂度分析 133
5.4.5内容小结 135
5.4.6思考题 135
5.5B+树:MySQL数据库索引是如何实现的 135
5.5.1典型需求:按值查询和按区间查询 135
5.5.2基于哈希表和二叉查找树的解决方案 136
5.5.3基于B+树的解决方案 136
5.5.4内容小结 139
5.5.5思考题 140
第6章堆 141
6.1堆:如何维护动态集合的最值 142
6.1.1堆的定义 142
6.1.2堆的存储 142
6.1.3往堆中插入元素 143
6.1.4删除堆顶元素 144
6.1.5删除任意元素 145
6.1.6堆的性能分析 145
6.1.7解答本节开篇问题 145
6.1.8内容小结 146
6.1.9思考题 146
6.2堆排序:为什么说堆排序没有快速排序快 147
6.2.1堆排序之建堆 147
6.2.2堆排序之排序 149
6.2.3堆排序的性能分析 149
6.2.4解答本节开篇问题 150
6.2.5内容小结 150
6.2.6思考题 151
6.3堆的应用:如何快速获取Top 10热门搜索关键词 151
6.3.1堆的应用1:优先级队列 151
6.3.2堆的应用2:求Top K 152
6.3.3堆的应用3:求中位数和百分位数 153
6.3.4解答本节开篇问题 155
6.3.5内容小结 155
6.3.6思考题 156
第7章跳表、并查集、线段树和树状数组 157
7.1跳表:Redis中的有序集合类型是如何实现的 158
7.1.1 跳表的由来 158
7.1.2 用跳表查询到底有多快 159
7.1.3 跳表是不是很浪费内存 160
7.1.4 高效插入和删除 161
7.1.5 跳表索引动态更新 162
7.1.6 解答本节开篇问题 162
7.1.7 内容小结 163
7.1.8 思考题 163
7.2并查集:路径压缩和按秩合并这两个优化是否冲突 163
7.2.1 并查集的由来 163
7.2.2 基于链表的实现思路 164
7.2.3 基于树的实现思路 166
7.2.4 内容小结 168
7.2.5 思考题 168
7.3线段树:如何查找猎聘网中积分排在第K位的猎头 168
7.3.1 区间统计问题 169
7.3.2 线段树的其他应用 172
7.3.3 解答本节开篇问题 174
7.3.4 内容小结 174
7.3.5 思考题 174
7.4树状数组:如何实现一个高性能、低延迟的实时排行榜 174
7.4.1 “前缀和”问题 175
7.4.2 树状数组与线段树的对比 177
7.4.3 解答本节开篇问题 177
7.4.4 内容小结 178
7.4.5 思考题 178
第8章字符串匹配算法 179
8.1BF算法:编程语言中的查找、替换函数是怎样实现的 180
8.1.1 BF算法的原理与实现 180
8.1.2 BF算法的性能分析 181
8.1.3 解答本节开篇问题 181
8.1.4 内容小结 182
8.1.5 思考题 182
8.2RK算法:如何借助哈希算法实现高效的字符串匹配 182
8.2.1 RK算法的原理与实现 182
8.2.2 RK算法的性能分析 183
8.2.3 内容小结 184
8.2.4 思考题 184
8.3BM算法:如何实现文本编辑器中的查找和替换功能 185
8.3.1 BM算法的核心思想 185
8.3.2 BM算法的原理分析 186
8.3.3 BM算法的代码实现 188
8.3.4 BM算法的性能分析 192
8.3.5 解答本节开篇问题 193
8.3.6 内容小结 193
8.3.7 思考题 193
8.4KMP算法:如何借助BM算法理解KMP算法 194
8.4.1 KMP算法的基本原理 194
8.4.2 失效函数的计算方法 196
8.4.3 KMP算法的性能分析 197
8.4.4 内容小结 198
8.4.5 思考题 198
8.5Trie树:如何实现搜索引擎的搜索关键词提示功能 198
8.5.1 Trie树的定义 199
8.5.2 Trie树的代码实现 200
8.5.3 Trie树的性能分析 201
8.5.4 Trie树与哈希表、红黑树的比较 202
8.5.5 解答本节开篇问题 202
8.5.6 内容小结 203
8.5.7 思考题 204
8.6AC自动机:如何用多模式串匹配实现敏感词过滤 204
8.6.1 基于单模式串的敏感词过滤 204
8.6.2 基于Trie树的敏感词过滤 205
8.6.3 基于AC自动机的敏感词过滤 205
8.6.4 AC自动机的性能分析 208
8.6.5 内容小结 209
8.6.6 思考题 209
第9章图 210
9.1图的表示:如何存储微博、微信等社交网络中的好友关系 211
9.1.1 图的定义 211
9.1.2 邻接矩阵的存储方法 212
9.1.3 邻接表的存储方法 213
9.1.4 解答本节开篇问题 214
9.1.5 内容小结 215
9.1.6 思考题 215
9.2深度优先搜索和广度优先搜索:如何找出社交网络中的三度好友关系 216
9.2.1 什么是搜索算法 216
9.2.2 广度优先搜索 217
9.2.3 深度优先搜索 219
9.2.4 解答本节开篇问题 220
9.2.5 内容小结 220
9.2.6 思考题 220
9.3拓扑排序:如何确定代码源文件的编译依赖关系 221
9.3.1 什么是拓扑排序 221
9.3.2 利用Kahn算法实现拓扑排序 222
9.3.3 利用深度优先搜索实现拓扑排序 222
9.3.4 利用拓扑排序检测环 223
9.3.5 解答本节开篇问题 224
9.3.6 内容小结 224
9.3.7 思考题 224
9.4单源最短路径:地图软件如何“计算”最优出行路线 225
9.4.1 最短路径算法介绍 225
9.4.2 Dijkstra算法的原理与实现 225
9.4.3 Dijkstra算法的性能分析 228
9.4.4 Dijkstra算法思想的应用 228
9.4.5 解答本节开篇问题 229
9.4.6 内容小结 230
9.4.7 思考题 230
9.5多源最短路径:如何利用Floyd算法解决传递闭包问题 231
9.5.1 Floyd算法的原理与实现 231
9.5.2 Floyd算法的性能分析 232
9.5.3 利用Floyd算法求解传递闭包 232
9.5.4 内容小结 233
9.5.5 思考题 233
9.6启发式搜索:如何用A*算法实现游戏中的寻路功能 233
9.6.1 什么是次优路线 234
9.6.2 A*算法的原理与实现 234
9.6.3 A*算法与Dijkstra算法的对比 236
9.6.4 解答本节开篇问题 237
9.6.5 内容小结 237
9.6.6 思考题 238
9.7最小生成树:如何随机生成游戏中的迷宫地图 238
9.7.1 什么是最小生成树 238
9.7.2 Kruskal算法的原理与实现 239
9.7.3 Prim算法的原理与实现 240
9.7.4 解答本节开篇问题 242
9.7.5 内容小结 244
9.7.6 思考题 245
9.8最大流:如何解决单身交友联谊中的最多匹配问题 245
9.8.1 什么是最大流 245
9.8.2 Ford-Fulkerson方法 246
9.8.3 Edmonds-Karp算法 247
9.8.4 最大二分匹配 249
9.8.5 解答本节开篇问题 249
9.8.6 内容小结 249
9.8.7 思考题 250
第10章贪心、分治、回溯和动态规划 251
10.1贪心算法:如何利用贪心算法实现霍夫曼编码 252
10.1.1 如何理解贪心算法 252
10.1.2 贪心算法的应用示例 253
10.1.3 解答本节开篇问题 255
10.1.4 内容小结 256
10.1.5 思考题 256
10.2分治算法:谈一谈大规模计算框架MapReduce中的分治思想 256
10.2.1 如何理解分治算法 257
10.2.2 分治算法的应用示例 257
10.2.3 分治算法在大数据处理中的应用 259
10.2.4 解答本节开篇问题 259
10.2.5 内容小结 260
10.2.6 思考题 260
10.3回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想 260
10.3.1 如何理解回溯算法 261
10.3.2 八皇后问题 261
10.3.3 0-1背包问题 262
10.3.4 正则表达式匹配问题 263
10.3.5 内容小结 264
10.3.6 思考题 264
10.4初识动态规划:如何巧妙解决“双11”购物时的凑单问题 264
10.4.1 动态规划的学习路线 265
10.4.2 利用动态规划解决0-1背包问题 265
10.4.3 0-1背包问题的升级版 269
10.4.4 解答本节开篇问题 270
10.4.5 内容小结 271
10.4.6 思考题 272
10.5动态规划理论:彻底理解最优子结构、无后效性和重复子问题 272
10.5.1 “一个模型和三个特征”理论介绍 272
10.5.2 “一个模型和三个特征”的应用示例 273
10.5.3 动态规划的两种解题方法 274
10.5.4 4种算法思想的比较分析 277
10.5.5 内容小结 277
10.5.6 思考题 278
10.6动态规划实战:如何实现搜索引擎中的拼写纠错功能 278
10.6.1 如何量化两个字符串的相似度 278
10.6.2 如何通过编程计算莱文斯坦距离 279
10.6.3 如何通过编程计算最长公共子串长度 281
10.6.4 解答本节开篇问题 282
10.6.5 内容小结 283
10.6.6 思考题 283
第11章数据结构和算法实战 284
11.1实战1:剖析Redis的常用数据类型对应的数据结构 285
11.1.1 Redis数据库介绍 285
11.1.2 列表(list) 285
11.1.3 哈希(hash) 286
11.1.4 集合(set) 286
11.1.5 有序集合(sorted set) 287
11.1.6 数据结构的持久化问题 287
11.1.7 总结和引申 288
11.1.8 思考题 288
11.2实战2:剖析搜索引擎背后的经典数据结构和算法 288
11.2.1 搜索引擎系统的整体介绍 288
11.2.2 搜集 289
11.2.3 分析 290
11.2.4 索引 292
11.2.5 查询 292
11.2.6 总结和引申 293
11.2.7 思考题 293
11.3实战3:剖析微服务鉴权和限流背后的数据结构和算法 293
11.3.1 鉴权背景介绍 294
11.3.2 如何实现快速鉴权 294
11.3.3 限流背景介绍 297
11.3.4 如何实现精准限流 297
11.3.5 总结和引申 298
11.3.6 思考题 299
11.4实战4:用学过的数据结构和算法实现短网址服务 299
11.4.1 短网址服务的整体介绍 299
11.4.2 通过哈希算法生成短网址 299
11.4.3 通过ID生成器生成短网址 302
11.4.4 总结和引申 303
11.4.5 思考题 303
附录A思考题答案 304