LABULADONG的算法笔记

本书约定 / 1 编程语言基础 / 4 第1章 核心框架篇 / 15 1.1 学习数据结构和算法的框架思维 15 1.1.1 数据结构的存储方式 16 1.1.2 数据结构的基本操作 17 1.1.3 算法刷题指南 18 1.2 计算机算法的本质 24 1.2.1 算法的本质 24 1.2.2 数组/ 单链表系列算法 26 1.2.3 二叉树系列算法 28 1.2.4 *后总结 33 1.3 动态规划解题套路框架 33 1.3.1 斐波那契数列 35 1.3.2 凑零钱问题 40 1.3.3 *后总结 45 1.4 回溯算法解题套路框架 46 1.4.1 全排列问题 47 1.4.2 N皇后问题 52 1.4.3 *后总结 55 1.5 BFS算法解题套路框架 55 1.5.1 算法框架 56 1.5.2 二叉树的*小高度 57 1.5.3 解开密码锁的*少次数 59 1.5.4 双向BFS 优化 62 1.6 手把手带你刷二叉树（纲领） 65 1.6.1 二叉树的重要性 66 1.6.2 深入理解前、中、后序 67 1.6.3 两种解题思路 71 1.6.4 后序位置的特殊之处 75 1.6.5 层序遍历 79 1.7 我写了首诗，保你闭着眼睛都能写出二分搜索算法 81 1.7.1 二分搜索框架 82 1.7.2 寻找一个数（基本的二分搜索） 82 1.7.3 寻找左侧边界的二分搜索 84 1.7.4 寻找右侧边界的二分搜索 88 1.7.5 逻辑统一 90 1.8 我写了一个模板，把滑动窗口算法变成了默写题 93 1.8.1 *小覆盖子串 96 1.8.2 字符串排列 100 1.8.3 找所有字母异位词 102 1.8.4 *长无重复子串 103 第2章 手把手刷数据结构 / 105 2.1 数组、链表 105 2.1.1 单链表的六大解题套路 105 2.1.2 数组双指针的解题套路 116 2.1.3 小而美的算法技巧：前缀和数组 124 2.1.4 小而美的算法技巧：差分数组 128 2.2 数据结构设计 134 2.2.1 算法就像搭乐高：带你手写LRU算法 135 2.2.2 算法就像搭乐高：带你手写LFU算法 144 2.2.3 以O(1) 时间复杂度删除/ 查找数组中的任意元素 151 2.2.4 单调栈结构解决三道算法题 159 2.2.5 单调队列结构解决滑动窗口问题 164 第3章 手把手培养算法思维 / 170 3.1 二叉树 170 3.1.1 手把手带你刷二叉树（思路） 170 3.1.2 手把手带你刷二叉树（构造） 179 3.1.3 手把手带你刷二叉树（序列化） 192 3.1.3 零、前/ 中/ 后序和二叉树的唯一性 193 3.1.4 归并排序详解及运用 206 3.2 二叉搜索树 215 3.2.1 手把手带你刷二叉搜索树（特性应用） 215 3.2.2 手把手带你刷二叉搜索树（增删查改） 220 3.2.3 快速排序详解及运用 227 3.3 图论算法 237 3.3.1 图论算法基础 237 3.3.2 Union-Find算法详解 245 3.3.3 *小生成树之 Kruskal算法 259 3.4 暴力搜索算法 268 3.4.1 回溯算法解决子集、排列、组合问题 268 3.4.2 经典回溯算法：集合划分问题 291 3.4.3 DFS算法搞定岛屿系列题目 305 3.4.4 BFS算法解决智力游戏 317 第4章 手把手刷动态规划 / 323 4.1 动态规划核心原理 323 4.1.1 base case 和备忘录的初始值怎么定 323 4.1.2 *优子结构和dp 数组的遍历方向怎么定 329 4.1.3 算法时空复杂度分析实用指南 338 4.1.4 动态规划的降维打击：空间压缩技巧 351 4.2 子序列类型问题 358 4.2.1 动态规划设计：*长递增子序列 358 4.2.2 详解*大子数组和 367 4.2.3 详解编辑距离问题 372 4.2.4 详解*长公共子序列问题 381 4.2.5 详解正则匹配问题 389 4.2.6 子序列问题解题模板 397 4.3 背包问题 404 4.3.1 0-1 背包问题解题框架 404 4.3.2 背包问题变体之子集分割 407 4.3.3 背包问题之零钱兑换 410 4.4 用动态规划玩游戏 414 4.4.1 *小路径和问题 414 4.4.2 动态规划算法通关《魔塔》 419 4.4.3 高楼扔鸡蛋问题 426 4.4.4 戳气球问题 438 第5章 高频面试系列 / 445 5.1 链表操作的递归思维一览 445 5.1.1 递归反转整个链表 446 5.1.2 反转链表前N 个节点 448 5.1.3 反转链表的一部分 449 5.2 田忌赛马背后的算法决策 450 5.3 一道数组去重的算法题把我整蒙了 454 5.4 带权重的随机选择算法 458 5.4.1 解法思路 459 5.4.2 解法代码 460 5.5 二分搜索题型套路分析 462 5.5.1 原始的二分搜索代码 463 5.5.2 二分搜索问题的泛化 465 5.5.3 运用二分搜索的套路框架 467 5.5.4 例题一：珂珂吃香蕉 468 5.5.5 例题二：运送货物 471 5.5.6 例题三：分割数组 474 5.6 如何高效解决接雨水问题 475 5.6.1 核心思路 476 5.6.2 备忘录优化 478 5.6.3 双指针解法 479 5.6.4 扩展延伸 481 5.7 一个函数解决nSum 问题 483 5.7.1 twoSum 问题 483 5.7.2 3Sum 问题 486 5.7.3 4Sum 问题 488 5.7.4 100Sum 问题 489 5.8 一个方法解决*近公共祖先问题 491 5.8.1 寻找一个元素 492 5.8.2 解决五道题目 495