代码随想录算法训练营 总结（持续更新）_代码随想录训练营

数组

二分查找

特征：有序数组

注意事项：

1. 确定循环中的不变量，并且在代码中一直保持。
2. 二分法的本质是根据是否满足题目的条件来缩小答案所在的区间，由此衍生出的变体也大多都在缩小区间的条件上做文章，要能识别二分法的本质与变化。
3. 代码实现：mid_idx = left_idx + (right_idx - left_idx >> 1) 可以避免 int overflow，同时 >> 1 的位运算比 //2 更快

有序数组的平方就是一道简单的二分查找的变形，要能迅速意识到并且使用二分查找。

移除元素

特征：有序数组

快慢指针是非常经典的数组方法，用快指针探路 + 慢指针填入来实现 in-place 的删除，获得$O(n)$的复杂度。

滑动窗口

特征：正数，非有序数组，但连续子数组同样要求了单调性

注意事项：

1. 连续子数组使得我们可以只关注右指针的移动，并通过条件来判断左指针的移动
2. 如果数组中有负数存在，则会退化成暴力解法。

螺旋矩阵

操作性题目，没有过多的技巧。注意要清楚识别每一个 case 的边界条件，保持思路清晰。

注意事项：

1. 根据自己的简单例子，清晰走一遍代码流程，一般就能得到正确答案。
2. 要清楚理解自己设置的每一个变量的含义。
3. recursion 也可以解决。

链表

虚拟头节点、双指针，堪称链表的两大杀器。

• 虚拟头节点可以轻松规避单独处理头节点的情况
• 双指针可以先探路、再修改指针，对于链表来说可以有效降低复杂度
• recursion 在链表中也非常好用

反转链表

双指针在链表中的经典作用，节约了空间。

两两交换链表中的节点

反转链表的进阶版。最重要的是理清思路，明白每一个变量的目的与含义。

链表相交

很有意思的一道题。经典解法非常简单，将两个链表尾部对齐，然后从对齐的开头同时遍历即可。还有另一个更巧妙的解法，利用了交叉点的特性。

环形链表II

快慢指针的巅峰之作（之一），也非常有趣。题目的解法有两个重点：

1. 如何找到循环
   • 如果不存在循环，快指针会直接领先慢指针抵达终点
   • 但存在循环的话，快指针在环内总会追上慢指针
2. 如何利用循环（找到环入口）
   • 需要进行数学推导，才能得到合理的结论
   • 最终的代码非常简洁，但这是建立在完备的数学推导之上的

哈希

使用时机：需要查询一个元素是否出现过，或者一个元素是否在集合里的时候
但是注意，哈希的优势在于查找元素（或者说查找索引），但并不关心元素的位置。当对元素位置有所要求时，哈希就会变的较为麻烦（例如三数之和、四数之和）。

• 数组：元素有明显范围限制（例如小写字母），优先使用数组
• set：元素无范围，可能有大跨度、稀疏，优先使用 set
• mapping（字典）：有明确的 key-value 对应关系，有许多便捷的子类可以使用；但注意 mapping 本身的复杂度就要比另外两者更高，所以不能无脑用

python 实现（API）

熟悉各种结构的 API 调用很重要！

set

• a.add(...)：向 set 中添加元素
• a & b：返回 a 和 b 中的共同元素

dictionary

• from collections import defaultdict, Counter：使用 dict 的子类时要记得 import。
• a = defaultdict(0)：定义一个字典 a，如果a[k]被执行时 k 并非 a 中的 key，则自动插入并令a[k]=0。
• dictionary.get(keyname, value)：从字典中获取 keyname 对应的值；如果 keyname 不存在，则返回 value。

Counter的用法

快乐数

本质还是判断元素是否出现，关键是要能透过题目看懂本质是在问哈希。

两数之和

要想明白为什么要用 mapping，同时 mapping 的 key 和 value 分别是什么。思路要清晰，再开始写哈希。

四数相加II

题目只关注元素的值，而不在意 index（索引），所以哈希是最优解，可以通过遍历的指针压缩到 $O(n^2)$。

三/四数相加

题目同时需要 index 和 value，这意味着哈希无法发挥全部优势，因为哈希只能关注两者中的一种（准确来说是检查 index 是否存在）。所以哈希的去重会变的非常复杂。
所以使用双指针，对输入排序（彻底告别哈希），固定多个遍历的指针，直到剩余两个进行头尾的双指针。
想到了双指针之后，题目的难点就剩下“正确去重”和“正确剪枝”。

栈和队列

• 栈：Last-In-First-Out
  • 栈的结构并不复杂，应用也较为简单
  • 栈的结构决定了很适合解决匹配类型的题目
• 队列：FIFO