编辑推荐
在你还没有拿得出手的实战项目证明自己能力时,面试官只能拿算法题评估你。力扣算法题因被BAT、京东、美团、字节跳动、滴滴、拼dd、微软、亚马逊、Google、Facebook等一线科技公司选作面试题而名声大噪,不论你是想拿下大厂Offer,还是想在技术道路上走得更远,刷算法题,尤其是刷力扣算法题,无疑是一个高效率的选择。
简单地会解某一道算法题并不意味着什么,因为很少有人能刷完力扣的上千道题,算法小抄把算法题分门别类汇总,提炼出各类题的解题框架,从而以不变应万变。
@程序员小灰等KOL力荐。
用喜闻乐见的语言讲述算法,书中配有几百幅有趣的算法图示,并送上部分动画演示。
内容简介
《labuladong的算法小抄》专攻算法刷题,训练算法思维,应对算法笔试。注重用套路和框架思维解决问题,以不变应万变。
第1章列举了几个最常见的算法类型及对应的解题框架思路,包括动态规划、回溯、广度优先搜索及双指针、滑动窗口等算法技巧。
第2章用动态规划的通用思路框架解决了十几道经典的动态规划问题,例如,正则表达式、背包问题,同时还介绍了如何写状态转移方程、如何进行状态压缩等技巧。
第3章介绍了数据结构相关的算法,例如,二叉树相关题目的解法,也包括LRU、LFU这种面试常考的算法原理。
第4章介绍了回溯算法、广度优先搜索算法等核心套路在算法题中的运用,巩固对算法框架的理解。
第5章讲解了一些高频题目,每道题目可能会结合多种算法思路进行讲解,也可能有多种解法,读完这一章,你就可以独自遨游题海啦!
作者简介
微信公众号labuladong的作者,有多年的刷题经验,希望用通俗的语言帮助广大互联网从业者少走弯路,快速从根本上攻克算法难关,为职业道路的发展赋能。
章节目录
第1章核心套路篇/ 21
1.1学习算法和刷题的框架思维/ 21
1.1.1数据结构的存储方式/ 21
1.1.2数据结构的基本操作/ 23
1.1.3算法刷题指南/ 25
1.1.4最后总结/ 30
1.2动态规划解题套路框架/ 31
1.2.1斐波那契数列/ 32
1.2.2凑零钱问题/ 37
1.2.3最后总结/ 42
1.3回溯算法解题套路框架/ 43
1.3.1全排列问题/ 43
1.3.2N 皇后问题/ 48
1.3.3最后总结/ 51
1.4BFS 算法套路框架/ 53
1.4.1算法框架/ 53
1.4.2二叉树的最小高度/ 54
1.4.3解开密码锁的最少次数/ 56
1.5双指针技巧套路框架/ 64
1.5.1快、慢指针的常用算法/ 64
1.5.2左、右指针的常用算法/ 68
1.6我写了首诗,保你闭着眼睛都能写出二分搜索算法/ 71
1.6.1二分搜索框架/ 72
1.6.2寻找一个数(基本的二分搜索)/ 73
1.6.3寻找左侧边界的二分搜索/ 75
1.6.4寻找右侧边界的二分搜索/ 79
1.6.5逻辑统一/ 82
1.7我写了一个模板,把滑动窗口算法变成了默写题/ 85
1.7.1最小覆盖子串/ 87
1.7.2字符串排列/ 91
1.7.3找所有字母异位词/ 93
1.7.4最长无重复子串/ 94
第2章动态规划系列/ 96
2.1动态规划设计:最长递增子序列/ 96
2.1.1动态规划解法/ 97
2.1.2二分搜索解法/ 100
2.2二维递增子序列:信封嵌套问题/ 104
2.2.1题目概述/ 104
2.2.2思路分析/ 105
2.2.3最后总结/ 107
2.3最大子数组问题/ 108
2.3.1思路分析/ 108
2.3.2最后总结/ 110
2.4动态规划答疑:最优子结构及dp 遍历方向/ 111
2.4.1最优子结构详解/ 111
2.4.2dp 数组的遍历方向/ 113
2.5经典动态规划:最长公共子序列/ 117
2.6经典动态规划:编辑距离/ 123
2.6.1思路分析/ 124
2.6.2代码详解/ 125
2.6.3动态规划优化/ 129
2.6.4扩展延伸/ 131
2.7子序列问题解题模板:最长回文子序列/ 136
2.7.1两种思路/ 136
2.7.2最长回文子序列/ 137
2.7.3代码实现/ 139
2.8状态压缩:对动态规划进行降维打击/ 141
2.9以最小插入次数构造回文串/ 148
2.9.1思路分析/ 148
2.9.2状态转移方程/ 149
2.9.3代码实现/ 152
2.10动态规划之正则表达式/ 155
2.10.1思路分析/ 155
2.10.2动态规划解法/ 157
2.11不同的定义产生不同的解法/ 162
2.11.1第一种思路/ 162
2.11.2第二种思路/ 165
2.11.3最后总结/ 167
2.12经典动态规划:高楼扔鸡蛋/ 168
2.12.1解析题目/ 168
2.12.2思路分析/ 169
2.12.3疑难解答/ 172
2.13经典动态规划:高楼扔鸡蛋(进阶)/ 173
2.13.1二分搜索优化/ 173
2.13.2重新定义状态转移/ 176
2.13.3还可以再优化/ 180
2.14经典动态规划:戳气球问题/ 181
2.14.1回溯思路/ 181
2.14.2动态规划思路/ 182
2.14.3写出代码/ 185
2.15经典动态规划:0-1 背包问题/ 188
2.16经典动态规划:子集背包问题/ 192
2.16.1问题分析/ 192
2.16.2思路分析/ 193
2.16.3进行状态压缩/ 194
2.17经典动态规划:完全背包问题/ 196
2.18题目千百变,套路不会变/ 200
2.18.1线性排列情况/ 200
2.18.2环形排列情况/ 203
2.18.3树形排列情况/ 205
2.19动态规划和回溯算法,到底是什么关系/ 207
2.19.1回溯思路/ 207
2.19.2消除重叠子问题/ 210
2.19.3动态规划/ 211
第3章数据结构系列/ 216
3.1手把手教你写 LRU 缓存淘汰算法/ 216
3.1.1LRU 算法描述/ 218
3.1.2LRU 算法设计/ 219
3.1.3代码实现/ 220
3.2层层拆解,带你手写LFU 算法/ 227
3.2.1算法描述/ 227
3.2.2思路分析/ 228
3.2.3代码框架/ 230
3.2.4LFU 核心逻辑/ 232
3.3二叉搜索树操作集锦/ 235
3.3.1判断 BST 的合法性/ 236
3.3.2在 BST 中查找一个数是否存在/ 238
3.3.3在 BST 中插入一个数/ 239
3.3.4在 BST 中删除一个数/ 239
3.4完全二叉树的节点数为什么那么难算/ 243
3.4.1思路分析/ 244
3.4.2复杂度分析/ 245
3.5用各种遍历框架序列化和反序列化二叉树/ 247
3.5.1题目描述/ 247
3.5.2前序遍历解法/ 248
3.5.3后序遍历解法/ 252
3.5.4中序遍历解法/ 255
3.5.5层级遍历解法/ 255
3.6Git 原理之二叉树最近公共祖先/ 260
3.6.1二叉树的最近公共祖先/ 261
3.6.2思路分析/ 263
3.7特殊数据结构:单调栈/ 266
3.7.1单调栈解题模板/ 266
3.7.2题目变形/ 268
3.7.3如何处理循环数组/ 268
3.8特殊数据结构:单调队列/ 271
3.8.1搭建解题框架/ 271
3.8.2实现单调队列数据结构/ 273
3.8.3算法复杂度分析/ 276
3.9如何判断回文链表/ 277
3.9.1判断回文单链表/ 277
3.9.2优化空间复杂度/ 280
3.9.3最后总结/ 282
3.10秀操作之纯递归反转链表/ 283
3.10.1递归反转整个链表/ 283
3.10.2反转链表前N 个节点/ 286
3.10.3反转链表的一部分/ 287
3.10.4最后总结/ 288
3.11秀操作之k 个一组反转链表/ 289
3.11.1分析问题/ 289
3.11.2代码实现/ 291
3.11.3最后总结/ 292
第4章算法思维系列/ 293
4.1回溯算法解决子集、组合、排列问题/ 293
4.1.1子集/ 293
4.1.2组合/ 297
4.1.3排列/ 299
4.2回溯算法最佳实践:解数独/ 301
4.2.1直观感受/ 301
4.2.2代码实现/ 301
4.3回溯算法最佳实践:括号生成/ 306
4.4BFS 算法暴力破解各种智力题/ 310
4.4.1题目解析/ 311
4.4.2思路分析/ 311
4.52Sum 问题的核心思想/ 315
4.5.12Sum I/ 315
4.5.22Sum II/ 316
4.5.3最后总结/ 318
4.6一个函数解决 nSum 问题/ 319
4.6.12Sum 问题/ 319
4.6.23Sum 问题/ 322
4.6.34Sum 问题/ 324
4.6.4100Sum 问题/ 325
4.7拆解复杂问题:实现计算器/ 328
4.7.1字符串转整数/ 328
4.7.2处理加减法/ 329
4.7.3处理乘除法/ 331
4.7.4处理括号/ 333
4.7.5最后总结/ 336
4.8摊烧饼也得有点递归思维/ 337
4.8.1思路分析/ 338
4.8.2代码实现/ 339
4.9前缀和技巧解决子数组问题/ 341
4.9.1什么是前缀和/ 341
4.9.2优化解法/ 343
4.9.3最后总结/ 344
4.10扁平化嵌套列表/ 345
4.10.1题目描述/ 345
4.10.2解题思路/ 346
4.10.3进阶思路/ 349
第5章高频面试系列/ 351
5.1如何高效寻找素数/ 351
5.2如何高效进行模幂运算/ 355
5.2.1如何处理数组指数/ 355
5.2.2如何处理 mod 运算/ 356
5.2.3如何高效求幂/ 358
5.3如何运用二分搜索算法/ 360
5.3.1问题分析/ 360
5.3.2扩展延伸/ 362
5.4如何高效解决接雨水问题/ 364
5.5如何去除有序数组的重复元素/ 371
5.6如何寻找最长回文子串/ 373
5.7如何运用贪心思想玩跳跃游戏/ 376
5.8如何运用贪心算法做时间管理/ 381
5.9如何判定括号合法性/ 386
5.10如何调度考生的座位/ 389
5.11Union-Find 算法详解/ 396
labuladong的算法小抄是2020年由电子工业出版社出版,作者付东来(@labuladong)。
得书感谢您对《labuladong的算法小抄》关注和支持,如本书内容有不良信息或侵权等情形的,请联系本网站。