LeetCode天梯
必做的leetcode题。
字符串
回文
最长回文子串
最经典的回文题，核心要点：
- 中心扩散方法
- 用封装函数（返回扩散后的长度）来进行奇数扩散和偶数扩散
这道题有一个对应的Manachar算法，时间复杂度可以缩短到O(n)，但是比较复杂，面试不需要写。但是可以说一下大致的思路：
- 统一格式，给所有字符之间加上#号，这样就不分奇偶情况了
字符串处理或几何模拟
Z字形变换
这道题展现了字符串处理时的巧思：我们人脑会把这种变换视为3D的动作，但实际上对于计算机来说，就相当于是把字符串分成了N个桶，然后对于一个字符串把字符不停放到各个桶中，放的顺序就是从第一个开始放到最后一个，放到最后一个后再返回第一个，如此往复。
我们可以用一个方向变量来控制是否“折返”，也可以用步长来控制：
- 用方向变了的话就相当于一个开关
- 用步长的话就是+1在边界处转换为-1
字符串转换整数（atoi）
这道题考察的和Z字形变化也比较像，主要就是考察状态的设定。这两道题都是简单的自动机，考察有限状态自动机的应用能力。
有限状态自动机看起来简单，实际写起来却很容易遗漏，所以这类题非常适合拿来考察逻辑完备性。这道题的leetcode通过率只有20%，算是一个经典的看起来简单、实操起来很容易出错的题。
二分搜索
二分排除法求第k小
两个正序数组的中位数
这道题对于正序刷leetcode的同学来说，相当于黑暗之魂3的古达，一上来就来一道看起来简单但是深思熟虑后发现事情没这么简单的题。
这道题有两个主流解法：
- 第K小逻辑的排除法（推荐用这个）
- 分割索引，运行速度理论最快，也是这道题的最佳实践，但是容易写错
第K小排除法的核心思路：
- 用递归思路，def getK(nums1, nums2, k)
- 核心逻辑是：我们总是比较两个数组的前k/2个数字，而且我们不需要考虑奇偶问题。被删掉的这些数，绝对不可能是全局第 \(k\) 小。因为即使把另一组更小的数都算上，这些被删掉的数最高排名也才第 \(k-1\)。
- 如果一个数组不够k/2长了，那么我们就取不够的那一个的最后一个，和另一个的k/2比较，依然是谁小就删除谁。假设A不够长，被删了，那么删掉了len(A)个，然后更新k位k-len(A)就行了。
- k是在不断变小的。\(k\) 代表的是“排名”。如果你通过比较，确定了其中一个队伍的前 4 个人肯定不是第 10 小（因为他们太靠前了），于是你把这 4 个人从候选名单里剔除了。既然已经有 4 个比目标小的数被你扔掉了，那么在剩下的所有人里，你原本要找的那个“全局第 10 小”，现在就变成了“剩下的人里的第 6 小”。所以，新的 \(k = 10 - 4 = 6\)。\(k\) 必须减去被扔掉的数字个数 ，这样它才能始终指向那个最初的目标。
- 终止条件：一个数组空了，代表结果在另一个数组中，并且就是第k个（迭代栈中的k）；要么就是k==1，说明要么是一个数组的头，要么是另一个数组的头。
- 第K个的数字的下标是K-1，这个写代码的时候很容易写错
值域二分法
binary search on value
单源最短路径
Dijkstra
网络延迟时间
LeetCode.743 Network Delay Time
考察点：最基础的dijkstra用法，即根据给定的图，求出源点到所有点的最短路径
有 \(N\) 个网络节点，给定一组带权有向边，求信号从 \(K\) 发出，传遍所有节点需要多久。标准的堆优化 Dijkstra 模板题。
Path with Minimum Effort
LeetCode.1631 Path with Minimum Effort
考察点：最小化最大化问题，matrix图的dijkstra
我们可以设定两个核心变量：
- diff：从当前格子走到邻居格子的高度绝对差
- effort：路径代价，即从源点出发到当前格子的路径上，所有曾经经历过的diff中的最大值（取决于最大的diff）
松弛条件：
如果 new_effort 比我们之前找到的到达 next 的代价更小，我们就更新它。这就是我们要“Minimize” (最小化) 的部分。
这道题要理解的是，最大值指的是路径上所经过的最大的地方；而最小值则指的是松弛的时候，我们要为每一个可能触达的新的邻居选择对他来说所有可走的路径中，effort最小的那一条。
这道题也可以转换为kruskal，从最小的边开始，直到kruskal上包含起点和终点。
变种：水位上升的水池中游泳
这道题是上面1631的变种，但是代表了另一种思想，直接想的话很容易想不出来。
1631直接给出了边权，但是778没有给出边权，这个时候就要稍微处理一下，人为构造边：“把进入这个点的代价，视为通向这个点的边的权重。”
- 在 1631 (边权) 中：
new_effort = max(current_effort, abs(height_A - height_B))(比较的是 差值 ) - 在 778 (点权) 中：
new_effort = max(current_effort, height_B)(比较的是 目标点本身的高度 )
A*
滑动拼图
这道题因为状态空间比较小，所以可以用BFS暴力解。BFS暴力解需要注意的必备知识点：
- 一维和二维的转换，用col作为转换的依据
- tuple不能直接修改，需要转换为list修改
- 找到邻居后，决定入队时，一定要入队邻居，这一点必须正确
在BFS暴力解后，我们思考该问题：BFS的空间复杂度是多少？
BFS 的搜索策略是“地毯式搜索”（Blind Search）。它必须把第 \(k\) 层的所有可能性全部存下来，才能去搜第 \(k+1\) 层。
假设平均每个状态有 3 个邻居（实际上是 2~4 个，取平均值 \(b \approx 3\)）。如果解在第 \(d\) 步：
- BFS 空间复杂度： \(O(b^d)\) （指数级增长）
对于2x3的棋盘，总状态数为\(6! = 720\) 种。对于3x3的8puzzle，总状态数：\(9! = 362,880\) 种（实际上只有一半可达，约 18 万）。解的最深步数约为 31 步。BFS 内存： 存 18 万个状态，几十 MB 内存。这几本已经达到极限。
对于4x4的puzzle，总状态数：\(16! \approx 20,000,000,000,000\) (20万亿)。解的最深步数约为 80 步。如果你要搜到第 80 层，\(3^{80}\) 是个天文数字。即便只搜到第 20 层，队列里可能就有 \(3^{20} \approx 34\) 亿个状态。结果： RAM 直接爆炸 。你的 32GB 内存条瞬间被吃光，程序崩溃。
3x3的puzzle解法：A*
BFS 是“盲搜”：不管三七二十一，先把第 1 层的邻居全看完，再看第 2 层。 A* 的核心在于“预测”： 它不按层走，而是按“总代价预估”走。
- \(g(n)\) (实际代价)： 从起点走到当前状态走了几步？（就是你的
cur_step）。 - \(h(n)\) (启发函数)： 预估从当前状态到终点还需要几步？（这是 A* 的灵魂）。
- \(f(n)\) (总优先级)： 越小越好。
对于滑动谜题，最常用的 \(h(n)\) 是 曼哈顿距离 (Manhattan Distance) ： 即：棋盘上每一个数字，离它“应该在的位置”，横向要走几步 + 纵向要走几步。 把所有数字的这个距离加起来，就是当前局面的 \(h(n)\)。
A*搜索重点关注以下几个内容：
- 启发式函数要计算所有位置和应到距离的和；其和可以理解为棋盘的混乱程度指数
- 0的距离不算在启发式函数h中
- 入队的cur_step就是g
- 总潜力f = g + h，入队的时候要给cur_step+1，因为入的是当前格子的邻居
- 入队判断和BFS一样，依然是只要不在visited中就入队，只不过入队的时候依据f
4x4的puzzle解法：IDA*
如果我们要解 \(4 \times 4\) (15-puzzle) 甚至 \(5 \times 5\)，普通的 A 还是会把内存撑爆（因为它要存 visited 集合）。这时候工业界使用的是 IDA (Iterative Deepening A )。它是 DFS（深度优先） 和 * A （启发式） * 的结合体。空间复杂度： \(O(d)\) （线性空间！）。它不需要 visited 集合，也不需要巨大的 priority_queue。如果解在第 80 层，它只需要存 80 个节点，内存占用几乎为零。
由于leetcode主要考察即使快写，模拟面试，因此IDA这种更加复杂的基本不会涉及到，所以对于这道题掌握BFS和写出启发函数来改进为A-star就足够了。
数值计算
数值溢出
整数反转
python中int是对象，可以自动扩容而不会物理溢出。但是在其他的一些语言中可能会溢出。所以一定要在计算的时候就检查是否溢出，如果溢出随时停止计算并return错误信号。
这里要注意，在 C、C++、Java 等语言中，如果一个 32 位有符号整数达到了最大值 \(2,147,483,647\) 再加 1，它会由于二进制位首位的符号位被改变，突然变成 最小的负数 。这个特性叫做数值环绕（Wraparound） 。