●章复杂度分析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.阻塞队列和并发队列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内容小结
3.4.6思考题
3.5O(nlogn)排序：如何借助快速排序思想快速查找第K大元素
3.5.1归并排序的原理和实现
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.解答本节开篇问题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.2JavaLinkedHashMap104
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堆的应用：如何快速获取0热门搜索关键词151
6.3.1堆的应用1：优先级队列151
6.3.2堆的应用2：求TopK152
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基于链表的实现思路1
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.1BF算法的原理与实现180
8.1.2BF算法的性能分析181
8.1.3解答本节开篇问题181
8.1.4内容小结182
8.1.5思考题182
8.2RK算法：如何借助哈希算法实现高效的字符串匹配182
8.2.1RK算法的原理与实现182
8.2.2RK算法的性能分析183
8.2.3内容小结184
8.2.4思考题184
8.3BM算法：如何实现文本编辑器中的查找和替换功能185
8.3.1BM算法的核心思想185
8.3.2BM算法的原理分析186
8.3.3BM算法的代码实现188
8.3.4BM算法的性能分析192
8.3.5解答本节开篇问题193
8.3.6内容小结193
8.3.7思考题193
8.4KMP算法：如何借助BM算法理解KMP算法194
8.4.1KMP算法的基本原理194
8.4.2失效函数的计算方法196
8.4.3KMP算法的性能分析197
8.4.4内容小结198
8.4.5思考题198
8.5Trie树：如何实现搜索引擎的搜索关键词提示功能198
8.5.1Trie树的定义199
8.5.2Trie树的代码实现200
8.5.3Trie树的性能分析201
8.5.4Trie树与哈希表、红黑树的比较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.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.2Dijkstra算法的原理与实现225
9.4.3Dijkstra算法的性能分析228
9.4.4Dijkstra算法思想的应用228
9.4.5解答本节开篇问题229
9.4.6内容小结230
9.4.7思考题230
9.5多源短路径：如何利用Floyd算法解决传递闭包问题231
9.5.1Floyd算法的原理与实现231
9.5.2Floyd算法的性能分析232
9.5.3利用Floyd算法求解传递闭包232
9.5.4内容小结233
9.5.5思考题233
9.6启发式搜索：如何用A*算法实现游戏中的寻路功能233
9.6.1什么是次优路线234
9.6.2A*算法的原理与实现234
9.6.3A*算法与Dijkstra算法的对比236
9.解答本节开篇问题237
9.6.5内容小结237
9.6.6思考题238
9.7小生成树：如何随机生成游戏中的迷宫地图238
9.7.1什么是小生成树238
9.7.2Kruskal算法的原理与实现239
9.7.3Prim算法的原理与实现240
9.7.4解答本节开篇问题242
9.7.5内容小结244
9.7.6思考题245
9.8流：如何解决单身交友联谊中的多匹配问题245
9.8.1什么是流245
9.8.2Ford-Fulkerson方法246
9.8.3Edmonds-Karp算法247
9.8.4二分匹配249
9.8.5解答本节开篇问题249
9.8.6内容小结249
9.8.7思考题250
0章贪心、分治、回溯和动态规划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.30-1背包问题262
10.3.4正则表达式匹配问题263
10.3.5内容小结2
10.3.6思考题2
10.4初识动态规划：如何巧妙解决“”购物时的凑单问题2
10.4.1动态规划的学习路线265
10.4.2利用动态规划解决0-1背包问题265
10.4.30-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.44种算法思想的比较分析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.解答本节开篇问题282
10.6.5内容小结283
10.6.6思考题283
1章数据结构和算法实战284
11.1实战1：剖析Redis的常用数据类型对应的数据结构285
11.1.1Redis数据库介绍285
11.1.2列表(list)285
11.1.3哈希(hash)286
11.1.4集合(set)286
11.1.5有序集合(sortedset)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