《算法小抄》读书笔记
2021-04-28 11:37:39 36 举报AI智能生成
希望用通俗的语言帮助广大互联网从业者少走弯路，快速从根本上攻克算法难关，为职业道路的发展赋能。
作者其他创作
大纲/内容
开篇词
学算法也好，学技术也好，我觉得做任何事情，一定要明白自己的目标是什么。
第一个关键词是「目标」，可以量化的才叫目标。
你想变有钱，想学好算法，这就叫无法量化的目标，有多少钱才算有钱，学到什么程度才算学好？量化的一个最大的特点是可以拆分。
比如说目标是进大厂，计划半年内刷 300 道题，那这可以反向拆分，每个月刷 50 道，工作日每天刷两道，休息日每天刷一道，再细化，每天几点到几点固定为刷题时间，期间屏蔽所有应用通知，专心做题思考；然后每天反省刷题计划是否达标，如果没达标，是为什么，怎么弥补。
这就是计算机的递归思维，自顶向下，逐步求精，反向求解。我们旧文写了很多动态规划相关的题目，基本都是先写自顶向下的递归解法，然后改写成自底向上的迭代解法，因为递归思路清晰嘛。
这就是计算机的递归思维，自顶向下，逐步求精，反向求解。我们旧文写了很多动态规划相关的题目，基本都是先写自顶向下的递归解法，然后改写成自底向上的迭代解法，因为递归思路清晰嘛。
第二个关键词是「明白」，不是说今天热血沸腾给自己制定计划，结果做着做着就被带偏了，真的明白应该是你每时每刻，每分每秒都明白目标是什么。
我指的被带偏不是说学着学着跑去刷抖音了，这种问题可以通过物理隔离等方法避免，我说的带偏是指方向跑偏。
比如说做英语阅读理解，见到一个不认识的词，就去查，这个过程中又见到十个不认识的词，然后又去查，结果一个小时过去了，查了不少单词，但是文章没读几句，题还没做。
你说他没学习，倒也认真学了，但是学着学着方向跑偏了，最后挂科了。
这就是没搞明白目标是啥，这种 DFS 查单词的事情，应该是背单词的时候去做，现在做阅读题呢，目标是快速理解文章内容，选出正确答案嘛。那么几个生僻词汇，影响你对全文内容的掌握吗？
算法到底是个什么定位，无非就是个锻炼思维能力，准备笔试面试的工具。
从个人的角度，学算法，也要时时刻刻「明白」自己想要的是啥。
如果目标就是从事算法相关的理论研究工作，去啃《算法导论》这种理论性很强的教材完全没问题，反正你还要在学术的路上走很多年，花上一两年打基础性价比挺高。
如果目标是找工作赚钱，那算法就起到个筛选作用，没必要啃大部头，我们号的风格就是你需要的。从各种算法的模板练起，配合历史文章边看边刷，总共可以刷掉将近两百题，国内大厂过算法关没什么问题。节约下来的时间，干点别的不香吗？
说实话我个人更倾向于后者，向钱看齐，那么算法只是个工具。有很多读者纠结于要不要打个竞赛刷个公开课之类的，我觉得大可不必，就好比你跑步，朝着终点直线冲刺最划算，非要跑 S 型秀个蛇皮走位，何苦呢？
人的精力真的是有限的，把每分每秒都压在刀刃上，才能更快达成目标不是么。
当然，不论选择什么，定好目标后都要仔细拆分，严格执行，这个就看个人的执行力了。
本文写了些方法论层面的东西，主要希望大家搞清楚自己学习的目标，制定自己的计划，有自己的思考。不要被乱七八糟的建议牵着鼻子走，今天查一个单词，明天查一个单词，结果到头来挂科了。
解决问题思路
遇到了什么问题、现象是什么、分析的思路、用了什么工具做了什么、最终解决问题的方案是什么。把这几个关键点理清楚，面试官问的时候就有条理地说出来，再根据对方的提问给出一些细节补充，这就能比较充分地体现出
不过，人生就是一个勇攀高峰的过程，不断拿下一个个山头。一个把未来看得重的人，无论处在什么阶段，难免都有烦恼和焦虑，都曾经怀疑过自己。但我想说，所谓的进步，不就是跳出舒适区嘛；要想往外跳，不舒适是很正常的，有压力说明你在进步，咬牙坚持下去，总有一天会好起来的。
学习方法
1、Pick a topic you want to understand and start studying it.选择一个学习主题，开始阅读关于它的所有资料，做必要的笔记。
2、Pretend to teachyour topic to a classroom.Make sure you're able to explain the topic in simple terms.假装你在教室里向学生解释这个主题，用尽量简单的词汇去描述它，力求学生能听懂。（听众可以是人，也可以是你的毛绒玩具）。
3、Go back to the books when you get stuck.当你讲解卡壳的时候，再回头阅读资料，弄清楚再继续讲解。
4、Simplify and use analogies.回到第一步，试图用更加简洁、直白的语言去讲述概念。
第零章、必读系列
我写了首诗，让你闭着眼睛也能写对二分搜索
1、分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
2、注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。
3、如需定义左闭右开的「搜索区间」搜索左右边界，只要在 nums[mid] == target 时做修改即可，搜索右侧时需要减一。
4、如果将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可，推荐拿小本本记下，作为二分搜索模板。
教你几招算法笔试的套路
避实就虚
概率大师
游戏参与者面对三扇门，其中两扇门后面是山羊，一扇门后面是跑车。参与者只要随便选一扇门，门后面的东西就归他（跑车的价值当然更大）。但是主持人决定帮一下参与者：在他选择之后，先不急着打开这扇门，而是由主持人打开剩下两扇门中的一扇，展示其中的山羊（主持人知道每扇门后面是什么），然后给参与者一次换门的机会，此时参与者应该换门还是不换门呢？
答案是应该换门，换门之后抽到跑车的概率是 2/3，不换的话是 1/3。
解法代码分层
简单说就是，不要把所有代码都写在 main 函数里面，我一直使用的套路是，main 函数负责接收数据，加一个 solution 函数负责统一处理数据和输出答案，然后再用诸如 backtrack 这样一个函数处理具体的算法逻辑。
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 主要负责接收数据
int N = scanner.nextInt();
int[][] orders = new int[N][2];
for (int i = 0; i < N; i++) {
orders[i][0] = scanner.nextInt();
orders[i][1] = scanner.nextInt();
}
// 委托 solution 进行求解
solution(orders);
}
static void solution(int[][] orders) {
// 排除一些基本的边界情况
if (orders.length == 0) {
System.out.println("None");
return;
}
// 委托 dp 函数执行具体的算法逻辑
int res = dp(orders, 0);
// 负责输出结果
System.out.println(res);
}
// 备忘录
static HashMap<String, Integer> memo = new HashMap<>();
static int dp(int[][] orders, int start) {
// 具体的算法逻辑
}
}
考前复习策略
应该尽可能多的看各种各样的题目，思考五分钟，想不出来解法的话直接看别人的答案。看懂思路就行了，甚至自己写一遍都没必要，因为比较浪费时间。
没有什么问题是暴力穷举解决不了的，直接用 回溯算法套路框架 硬上，大不了加个备忘录，不就成 动态规划套路框架 了么，再大不了这题我不做了么，暴力过上 60% 的 case 也挺 OK 的。
框架思维
「框架思维」，把每种算法的框架抽象出来，以不变应万变。
怎么培养框架思维，多刷多练多思考，最好能有思路指导。
比如，刷一道算法题，解题思路有什么可复用的地方，是否可以和之前做的某一道题联系起来？
再比如，都说动态规划问题难，千变万化，但这类问题本身是不是有一些特性，是不是能够抽象出一套抽象的指导方法来做动态规划问题？
第一章、动态规划系列
动态规划的一般流程就是三步：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。
找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系。
1.1 动态规划基本技巧
动态规划解题套路框架
题目
509.斐波那契数（简单）
322.零钱兑换（中等）
重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划问题一定会具备「最优子结构」
动态规划的穷举有点特别，因为这类问题存在「重叠子问题」
只有列出正确的「状态转移方程」才能正确地穷举
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。「状态压缩」
第一个斐波那契数列的问题，解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同而已。
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门
回溯法->递归树->重复子问题->备忘录/动态规划
一个模型三个特征
一个模型
多阶段决策最优解模型
我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
三个特征
1. 最优子结构
最优子结构指的是，问题的最优解包含子问题的最优解。
2. 无后效性
第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。
第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。3. 重复子问题
3. 重复子问题
不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。
两个常见的问题
1、到底什么才叫「最优子结构」，和动态规划什么关系。
最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的
2、为什么动态规划遍历dp数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历，有的无论咋遍历都是对的。
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
两种动态规划解题思路
回溯法(暴力解决)->递归树->重复子问题->备忘录/动态规划
1. 状态转移表法
二维的状态表，每个状态包含三个变量，行、列、数组值
根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。
回溯算法实现->定义状态->画递归树->找重复子问题->画状态转移表->根据递推关系填表->将填表过程翻译成代码
2. 状态转移方程法
状态转移方程是解决动态规划的关键
如果我们能写出状态转移方程，那动态规划问题基本上就解决一大半了
可以将转态转移方程转化为
递归加“备忘录”
迭代递推
找最优子结构->写状态转移方程->将状态转移方程翻译成代码
动态规划的两个思考方向：
1、自顶向下求解，称之为「记忆化递归」：初学的时候，建议先写「记忆化递归」的代码，然后把代码改成「自底向上」的「递推」求解；
2、自底向上求解，称之为「递推」或者就叫「动态规划」：在基础的「动态规划」问题里，绝大多数都可以从这个角度入手，做多了以后建议先从这个角度先思考，实在难以解决再考虑「记忆化递归」。
1.4 贪心类型问题
贪心算法之区间调度问题
贪心选择性质
每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一部分问题拥有这个性质。
限制值和期望值
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大
第二章、数据结构系列
2.1 整体学习思路
学习算法和数据结构的思路指南
从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。
一、数据结构的存储方式
数组（顺序存储）和链表（链式存储）
数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
递归的思想，自顶向下，从抽象到具体
散列表、栈、队列、堆、树、图都属于「上层建筑」，而数组和链表才是「结构基础」
「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
「跳表」就是链表加多级索引的结构，Redis中用跳表实现有序集合，是一种各方面性能都比较优秀的动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。
「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。
二、数据结构的基本操作
基本操作无非遍历 + 访问，再具体一点就是：增删查改。
数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。
各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。
线性就是 for/while 迭代为代表，非线性就是递归为代表。
数组遍历框架，典型的线性迭代结构：void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}
}
链表遍历框架，兼具迭代和递归结构：/* 基本的单链表节点 */
class ListNode {
int val;
ListNode next;
}
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代访问 p.val
}
}
void traverse(ListNode head) {
// 递归访问 head.val
traverse(head.next);
}
二叉树遍历框架，典型的非线性递归遍历结构：/* 基本的二叉树节点 */
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
}
二叉树框架可以扩展为 N 叉树的遍历框架：/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child);
}
所谓框架，就是套路。不管增删查改，这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了
三、算法刷题指南
首先要明确的是，数据结构是工具，算法是通过合适的工具解决特定问题的方法。
先刷二叉树，为什么要先刷二叉树呢，因为二叉树是最容易培养框架思维的，而且大部分算法技巧，本质上都是树的遍历问题。递归是解决树相关问题的最有效和最常用的方法之一
几乎所有二叉树的题目都是一套这个框架就出来了。void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
一旦出现树的层次遍历，都可以用队列作为辅助结构
自顶向下
1. return specific value for null node
2. update the answer if needed // answer <-- params
3. left_ans = top_down(root.left, left_params) // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params) // right_params <-- root.val, params
5. return the answer if needed // answer <-- left_ans, right_ans
自底向上
1. return 0 if root is null // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1 // return depth of the subtree rooted at root
当遇到树问题时，请先思考一下两个问题：
你能确定一些参数，从该节点自身解决出发寻找答案吗？
你可以使用这些参数和节点本身的值来决定什么应该是传递给它子节点的参数吗？
如果答案都是肯定的，那么请尝试使用 “自顶向下” 的递归来解决此问题。
或者你可以这样思考：对于树中的任意一个节点，如果你知道它子节点的答案，你能计算出该节点的答案吗？ 如果答案是肯定的，那么 “自底向上” 的递归可能是一个不错的解决方法。
数据结构的基本存储方式就是链式和顺序两种，基本操作就是增删查改，遍历方式无非迭代和递归。
学习数据结构和算法读什么书2020.12.8
二分图。简单来说，二分图就是一幅拥有特殊性质的图：能够用两种颜色为所有顶点着色，使得任何一条边的两个顶点颜色不同。
886. 可能的二分法 中等 https://leetcode-cn.com/problems/possible-bipartition/
《算法第 4 版》
算法学习之路
一、这是啥？
动手实现一个「队列」「栈」之类的数据结构，就能捅破这层窗户纸。数据结构无非就是数组、链表为骨架的一些特定操作而已；每个数据结构实现的功能无非增删查改罢了。
比如说「列队」这个数据结构，无非就是基于数组或者链表，实现 enqueue 和 dequeue 两个方法。这两个方法就是增和删呀，连查和改的方法都不需要。
二、有啥用？
解决这个问题，就涉及算法的设计了，是个持久战，需要经常进行抽象思考，刷算法题，培养「计算机思维」。
算法就是对数据结构准确而巧妙的运用。
常用算法问题也就那几大类，算法题无非就是不断变换场景，给那几个算法框架套上不同的皮。
刷题，就是在锻炼你的眼力，看你能不能看穿问题表象揪出相应的解法框架。
比如说，让你求解一个迷宫，你要把这个问题层层抽象：迷宫 -> 图的遍历 -> N 叉树的遍历 -> 二叉树的遍历。然后让框架指导你写具体的解法。
抽象问题，直击本质，是刷题中你需要刻意培养的能力。
三、如何看《算法第 4 版》
不要蜻蜓点水，这本书你能选择性的看上 50%，基本上就达到平均水平了
别怕这本书厚，因为起码有三分之一不用看
自顶向下，逐步求精
可以按顺序学习。书中正文的算法代码一定要亲自敲一遍，因为这些真的是扎实的基础，要认真理解。不要以为自己看一遍就看懂了，不动手的话理解不了的。
书中的数学证明，如不影响对算法本身的理解，完全可以跳过
章节最后的练习题，也可以全部跳过
抓大放小，着重理解整体的知识架构，而忽略证明、练习题这种细节问题，即保持自己对新知识的好奇心，避免陷入无限的细节被劝退。
四、如何刷题
尽量刷英文版的 LeetCode
强烈建议从 Explore 菜单里最下面的 Learn 开始刷，这个专题就是专门教你学习数据结构和基本算法的，教学篇和相应的练习题结合，不要太良心。
最好一个分类一个分类的刷，不要蜻蜓点水。比如说这几天就刷链表，刷完链表再去连刷几天二叉树。这样做是为了帮助你提取「框架」。一旦总结出针对一类问题的框架，解决同类问题可谓是手到擒来。
2.2 手把手刷链表题目（训练递归思维）
递归反转链表的一部分
92. 反转链表 II 中等 https://leetcode-cn.com/problems/reverse-linked-list-ii/
先用递归反转从head到n个的区间。然后再一层递归把m前进到1的位置
如何k个一组反转链表
25. K 个一组翻转链表 困难 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
(前序遍历)链表是一种兼具递归和迭代性质的数据结构。分区间反转，先写节点到节点之间的反转，然后递归调用本书反转每一部分
如何判断回文链表
234. 回文链表 简单 https://leetcode-cn.com/problems/palindrome-linked-list/
(后序遍历)递归后序遍历，第一个和最后一个比较，结束条件就是传入的right到前面，也就是为null，利用了递归函数的堆栈
2、先通过「双指针技巧」中的快慢指针来找到链表的中点。 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步。从slow开始反转后面的链表，现在就可以开始比较回文串了。
2.3 手把手刷二叉树（训练递归思维）
手把手带你刷二叉树（第一期）
快速排序就是个二叉树的前序遍历
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
归并排序就是个二叉树的后续遍历
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
/************************/
}
二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情，是自顶向下（前序遍历），还是自底向上（后序遍历）
226. 翻转二叉树 https://leetcode-cn.com/problems/invert-binary-tree/
前序遍历
116. 填充每个节点的下一个右侧节点指针 https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
前序遍历
114. 二叉树展开为链表 https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
后序遍历
递归算法的关键要明确函数的定义，相信这个定义，而不要跳进递归细节。
写二叉树的算法题，都是基于递归框架的，我们先要搞清楚 root 节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。
手把手带你刷二叉树（第二期）
把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了，我们千万不要跳进递归的细节里，你的脑袋才能压几个栈呀。
手把手带你刷二叉树（第三期）
根据题意，思考一个二叉树节点需要做什么，到底用什么遍历顺序就清楚了。
手把手带你刷二叉搜索树（第一期）
二叉搜索树（Binary Search Tree，后文简写 BST），BST 的中序遍历结果是有序的（升序）。
538. 把二叉搜索树转换为累加树1038. 把二叉搜索树转换为累加树
BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求
手把手带你刷二叉搜索树（第二期）
BST 代码框架
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}
二叉树的序列化，就那几个框架，枯燥至极
层级遍历二叉树的代码框架
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
297. 二叉树的序列化与反序列化
1、前序遍历解法
2、后序遍历解法
3、中序遍历解法
4、层级遍历解法
题目不让我干什么，我偏要干什么
341. 扁平化嵌套列表迭代器 https://leetcode-cn.com/problems/flatten-nested-list-iterator/
构建N 叉树，然后递归实现
2.4 手把手设计数据结构
Union-Find算法
常说的并查集算法，主要是解决图论中「动态连通性」问题的。
class UF {
/* 将 p 和 q 连接 */
public void union(int p, int q);
/* 判断 p 和 q 是否连通 */
public boolean connected(int p, int q);
/* 返回图中有多少个连通分量 */
public int count();
}
简单说，动态连通性其实可以抽象成给一幅图连线。
1、自反性：节点p和p是连通的。
2、对称性：如果节点p和q连通，那么q和p也连通。
3、传递性：如果节点p和q连通，q和r连通，那么p和r也连通。
Union-Find 算法，用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？
把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。
平衡性优化
我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个size数组，记录每棵树包含的节点数，我们不妨称为「重量」
路径压缩
进行路径压缩
parent[x] = parent[parent[x]];
130.被围绕的区域（中等）
990.等式方程的可满足性（中等）
使用 Union-Find 算法，主要是如何把原问题转化成图的动态连通性问题。对于算式合法性问题，可以直接利用等价关系，对于棋盘包围问题，则是利用一个虚拟节点，营造出动态连通特性。
很多更复杂的 DFS 算法问题，都可以利用 Union-Find 算法更漂亮的解决。
算法就像搭乐高：带你手撸 LRU 算法（Least Recently Used）
1、显然 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；
3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap（这是java里面的，在c#里面需要自己实现）。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。
分析上面的 3 个条件
1、如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
2、对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
3、链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。
注意我们实现的双链表 API 只能从尾部插入，也就是说靠尾部的数据是最近使用的，靠头部的数据是最久为使用的。
FIFO( First Input First Output)
算法就像搭乐高：带你手撸 LFU 算法（Least Frequently Used）
LinkedHashSet（这是java里面的，在c#需要自己实现）
一道求中位数的算法题把我整不会了
295.数据流的中位数（困难）
使用两个优先级队列，PriorityQueue，维护一个大顶堆和一个小顶堆，两个堆中的元素之差不能超过 1
设计朋友圈时间线功能
355.设计推特（中等）
如果我们把每个用户各自的推文存储在链表里，每个链表节点存储文章 id 和一个时间戳 time（记录发帖时间以便比较），而且这个链表是按 time 有序的，那么如果某个用户关注了 k 个用户，我们就可以用合并 k 个有序链表的算法合并出有序的推文列表，正确地 getNewsFeed 了！
User 类
Tweet 类
实现合并 k 个有序链表的算法需要用到优先级队列（Priority Queue），这种数据结构是「二叉堆」最重要的应用，你可以理解为它可以对插入的元素自动排序。乱序的元素插入其中就被放到了正确的位置，可以按照从小到大（或从大到小）有序地取出元素。
单调栈结构解决三道算法题
单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。只处理一种典型的问题，叫做 Next Greater Element。
496. 下一个更大元素 I 简单
503. 下一个更大元素 II 中等
739. 每日温度 中等
单调队列结构解决滑动窗口问题
观察滑动窗口的过程就能发现，实现「单调队列」必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显双链表是满足这个条件的。
239. 滑动窗口最大值
「单调队列」的核心思路和「单调栈」类似，push 方法依然在队尾添加元素，但是要把前面比自己小的元素都删掉
一个「队列」，使得队列中的元素全都是单调递增（或递减）的
二叉堆，实现优先级队列
二叉堆其实就是一种特殊的二叉树（完全二叉树），存储在数组里，把数组索引作为指针
二叉堆还分为最大堆和最小堆。最大堆的性质是：每个节点都大于等于它的两个子节点。类似的，最小堆的性质是：每个节点都小于等于它的子节点。
优先级队列这种数据结构有一个很有用的功能，你插入或者删除元素的时候，元素会自动排序，底层的原理就是二叉堆的操作。
优先级队列有两个主要 API，分别是insert插入一个元素和delMax删除最大元素（如果底层用最小堆，那么就是delMin）。
2.5 手把手刷数组题目
如何运用二分查找算法（只要涉及到可以通过穷举来遍历解决的题目都可以用二分法进行计算来将时间复杂度达到为 O(NlogN)）
875.爱吃香蕉的珂珂（中等）
速度是speed
最少为 1，最大为 max(piles)
从 1 开始穷举到 max(piles)，一旦发现发现某个值可以在 H 小时内吃完所有香蕉，这个值就是最小速度：
int minEatingSpeed(int[] piles, int H) {
// piles 数组的最大值
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// 以 speed 是否能在 H 小时内吃完香蕉
if (canFinish(piles, speed, H))
return speed;
}
return max;
}
for 循环，就是在连续的空间线性搜索，这就是二分查找可以发挥作用的标志。由于我们要求的是最小速度，所以可以用一个搜索左侧边界的二分查找来代替线性搜索，提升效率：
public int minEatingSpeed(int[] piles, int H) {
// 套用搜索左侧边界的算法框架
int left = 1, right = getMax(piles) + 1;
while (left < right) {
// 防止溢出
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 时间复杂度 O(N)
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
int timeOf(int n, int speed) {
return (n / speed) + ((n % speed > 0) ? 1 : 0);
}
int getMax(int[] piles) {
int max = 0;
for (int n : piles)
max = Math.max(n, max);
return max;
}
1011. 在 D 天内送达包裹的能力
最小载重 cap
首先确定 cap 的最小值和最大值分别为 max(weights) 和 sum(weights)
我们要求最小载重，所以可以用搜索左侧边界的二分查找算法优化线性搜索
public int shipWithinDays(int[] weights, int D) {
// 载重可能的最小值
int left = getMax(weights);
// 载重可能的最大值 + 1
int right = getSum(weights) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 如果载重为 cap，是否能在 D 天内运完货物？
boolean canFinish(int[] w, int D, int cap) {
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= w[i]) >= 0) {
i++;
if (i == w.length)
return true;
}
}
return false;
}
int getMax(int[] piles) {
int max = 0;
for (int n : piles)
max = Math.max(n, max);
return max;
}
int getSum(int[] piles) {
int sum = 0;
for (int n : piles)
sum += n;
return sum;
}
双指针技巧总结
把双指针技巧再分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。
「快慢指针」
141. 环形链表
经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
142. 环形链表 II
fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
876. 链表的中间结点
让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
19. 删除链表的倒数第N个节点
让快指针先走 n 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 n 个链表节点（n 不会超过链表长度）。
「左右指针」
1、二分查找
167. 两数之和 II - 输入有序数组
344. 反转字符串
滑动窗口技巧
int left = 0, right = 0;
while (right < s.size()) {`
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
一、最小覆盖子串
76. 最小覆盖子串 困难
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
二、字符串排列
567. 字符串的排列 中等
明显的滑动窗口算法，相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，应为排列嘛，显然长度应该是一样的。
2、当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
三、找所有字母异位词
438. 找到字符串中所有字母异位词
相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
四、最长无重复子串
给我O(1)时间，我可以删除/查找数组中的任意元素
思路
1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。
3、对于第二题，数组中含有「空洞」（黑名单数字），也可以利用哈希表巧妙处理映射关系，让数组在逻辑上是紧凑的，方便随机取元素。
2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。
题目
380.常数时间插入、删除和获取随机元素（中等）
710.黑名单中的随机数（困难）
数组去重(数组去重的最高境界)
316. 去除重复字母
1081. 不同字符的最小子序列
要求一、通过inStack这个布尔数组做到栈stk中不存在重复元素。
要求二、我们顺序遍历字符串s，通过「栈」这种顺序结构的 push/pop 操作记录结果字符串，保证了字符出现的顺序和s中出现的顺序一致。
这里也可以想到为什么要用「栈」这种数据结构，因为先进后出的结构允许我们立即操作刚插入的字符，如果用「队列」的话肯定是做不到的。
要求三、我们用类似单调栈的思路，配合计数器count不断 pop 掉不符合最小字典序的字符，保证了最终得到的结果字典序最小。
当然，由于栈的结构特点，我们最后需要把栈中元素取出后再反转一次才是最终结果。
第三章、必会算法技巧15篇
3.1 回溯算法（DFS 算法）篇
回溯算法解题套路框架
题目
46.全排列（中等）
51.N皇后（困难）
思考 3 个问题
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
框架
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」
不管怎么优化，时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。
回溯算法团灭子集、排列、组合问题
78.子集（中等）
46.全排列（中等）
77.组合（中等）
回溯算法最佳实践：解数独
37.解数独（困难）
回溯算法最佳实践：括号生成
22.括号生成（中等）
1、一个「合法」括号组合的左括号数量一定等于右括号数量
2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量
3.2 BFS 算法篇
BFS 算法解题套路框架
题目
111.二叉树的最小深度（简单）
752.打开转盘锁（中等）
BFS 的核心思想，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多
益智游戏克星：BFS暴力搜索算法
773.滑动谜题（困难）
将滑动拼图游戏转化成 BFS 算法
二维数组有「上下左右」的概念，压缩成一维
BFS 算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举的问题，BFS 就可以用，而且可以最快地找到答案。
其他算法篇
差分数组/前缀和
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
560.和为K的子数组（中等）
快速排序亲兄弟：快速选择算法
215.数组中的第 K 个最大元素（中等）
二叉堆的解法比较简单，实际写算法题的时候，推荐大家写这种解法
快速选择算法比较巧妙，时间复杂度更低，是快速排序的简化版，相当于在快速排序中做二分查找
分治算法详解：表达式的不同优先级
先「分」后「治」，先按照运算符将原问题拆解成多个子问题，然后通过子问题的结果来合成原问题的结果。
241.为运算表达式设计优先级（中等）
最典型的分治算法就是归并排序
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
/****** 分 ******/
// 对数组的两部分分别排序
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 治 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
}
烧饼排序算法
969.煎饼排序（中等）
递归
第四章、高频面试系列15篇
4.1 数学运算技巧
如何在无限序列中随机抽取元素
382.链表随机节点（中等）
398.随机数索引（中等）
先说结论，当你遇到第 i 个元素时，应该有 1/i 的概率选择该元素，1 - 1/i 的概率保持原有的选择。
如何去除有序数组的重复元素
数组和链表都可以使用双指针
83. 删除排序链表中的重复元素 简单
26. 删除排序数组中的重复项 简单
一行代码就能解决的算法题
292.Nim游戏（简单）
877.石子游戏（中等）
319.灯泡开关（中等）
4.2 其他经典问题
如何寻找最长回文子串
二分查找高效判定子序列
392.判断子序列（简单）
利用双指针 i, j 分别指向 s, t，一边前进一边匹配子序列
t 进行预处理，用一个字典 index 将每个字符出现的索引位置按顺序存储下来，借助 index 中记录的信息，可以二分搜索 index[c] 中比 j 大的那个索引
第五章、技术文章系列8篇
收藏
收藏
0 条评论
下一页
