算法手写先练哪些？从链表、滑动窗口到动态规划

用滑动窗口加字符最近出现位置表，维护一个没有重复字符的连续区间。右端逐个加入字符；如果这个字符上一次出现在当前窗口内，就把左端移到上次位置之后，再更新最大长度。

关键是左端只能前进：left = max(left, 上次位置 + 1)。这样既能去掉当前重复，又不会因为遇到窗口外的旧字符而退回。哈希表操作按平均常数时间计算，整体时间为 O(n)，额外空间为 O(min(n, 字符集大小))。

题目求的是连续的子串长度。例如 pwwkew 的答案为 3，wke 连续且无重复；pwke 虽然无重复，却不是连续子串。

LRU（Least Recently Used）在容量不足时，淘汰距离上次使用最久的条目。 为了高效查找和调整使用顺序，我会用哈希表与双向链表配合实现：

• 哈希表 key → 节点：按 key 定位条目，节点保存 key、value 及前后指针。
• 双向链表：维护最近使用顺序，头部最近使用，尾部最久未用。

三个关键操作是：

1. 读取 get：命中后把节点移到头部，再返回值；未命中不改变顺序。
2. 写入 put：已有 key 就更新原节点的值并移到头部；新 key 就创建节点，加入哈希表并放到链表头部。
3. 超容量淘汰：删除链表尾部最久未使用的条目，并同步删除哈希表记录，保持两种结构一致。

哈希表必须保存节点，而不只是值，这样定位后就能通过前后指针直接摘除和插入，无须遍历链表。哈希查找平均 O(1)，这些链表操作只修改固定数量的指针，所以 get、put 的平均时间复杂度都是 O(1)。

利用两个数组已经有序的条件，用双指针逐个确定下一项，时间为 O(m+n)。 允许返回新数组时，从两边开头比较，把较小者追加到结果；一边用完，再接上另一边剩余部分。

如果要求写回第一个数组，且其尾部已预留足够空间，就从后往前比较有效区间的末尾，把较大者写到结果末尾。这样不会覆盖尚未读取的输入，额外空间可以降到 O(1)。

反转单链表，就是原地改变每个节点的 next 指向，再返回原尾节点作为新头。 用 prev 保存已反转部分的头，curr 指向待处理节点；每轮先保存原后继，再把 curr.next 指向 prev，最后推进指针。

结束时 curr=None，prev 就是新头。每个节点处理一次，时间 O(n)；迭代写法额外空间 O(1)，不需要新建节点或交换节点值。

可以使用快慢指针：两个指针都从头节点出发，slow 每轮走一步，fast 每轮走两步。移动后若指向同一个节点，说明有环；如果快指针或它的下一节点为空，则无环。

有环时，慢指针最终进入环中，此后快指针相对慢指针每轮前进一个节点，必然在有限轮内追上。时间复杂度是 O(n)，额外空间是 O(1)，其中 n 是从头节点能够到达的不同节点数。

比较的是节点身份，而不是节点值。两个不同节点即使都存了数字 1，也不代表形成环；判断过程中也不需要修改链表。

层序遍历用队列做广度优先搜索，按从上到下、每层从左到右的顺序访问节点。 根节点先入队，每次从队首取出节点，再依次把非空左孩子、右孩子加入队尾。

如果结果需要按层分组，每轮先记录当前队列长度，只处理这么多个节点；本轮加入的孩子留到下一轮。空树返回空列表。每个节点入队、出队各一次，时间复杂度为 O(n)；辅助队列占 O(w)，w 为最大层宽，保存全部结果另需 O(n)。

把陆地格子看作图的节点，上下左右相邻的陆地之间有边，岛屿数量就是陆地连通分量的数量。

遍历整个网格，每遇到一块尚未访问的陆地，就将岛屿数加一，并用 BFS 或 DFS 标记与它连通的全部陆地。后续扫描再遇到这些格子时直接跳过，因此每座岛只计数一次。

下面采用迭代 BFS，避免大岛屿造成递归调用过深。对于 m 行 n 列网格，时间复杂度为 O(mn)，使用访问数组和队列时，额外空间复杂度为 O(mn)。

快速排序先选一个基准值，把数组按它分区，再递归处理较小和较大的部分。**分区只保证两侧与基准的大小关系，不保证两侧内部已经有序。**当待排区间为空或只剩一个元素时结束。

一种适合重复值的实现是三路分区：把当前区间整理成“小于基准、等于基准、大于基准”三段，等于段无需继续排序，只处理另外两段。下面随机选基准，并把较长一侧改为循环、只递归较短一侧，控制调用栈深度。

在随机选基准的通常分析下，期望时间为 O(n log n)，仍有 O(n²) 的最坏时间；这里的三路写法在全相等输入上只需扫描一遍。代码原地修改数组，递归栈最坏为 O(log n)，不属于稳定排序。

可以用中心扩展法：回文子串关于中心对称，枚举每个字符作为奇数长度回文的中心，再枚举相邻字符之间的位置作为偶数长度回文的中心。每次从中心向两边比较，相等就继续扩展，遇到不相等或越界时停止，并记录最长区间。

这样不会漏掉奇数或偶数回文。最坏有 O(n) 个中心，每个中心扩展 O(n) 次，因此时间为 O(n²)；只记录下标和长度，额外工作空间为 O(1)，最终返回字符串所需空间另计。

例如 babad 可以返回 bab 或 aba；cbbd 应返回 bb，只检查单字符中心会漏掉这种偶数长度答案。题目要求连续子串，不能通过跳过中间字符拼出回文子序列。

用 Kadane 动态规划一次扫描。令 end 表示“必须以当前位置结尾的非空连续子数组”的最大和；遇到 x 时，选择从 x 重新开始，或接到上一段后面，即 end=max(x,end+x)。再用 best 记录遍历过的最大 end，时间O(n)、额外空间O(1)。

初始化为第一个元素，才能正确处理全负数组；不能把答案初始为0，否则会错误地选择题目不允许的空子数组。

通常按 Levenshtein 编辑距离回答：允许插入、删除、替换一个字符，每次成本为 1，求把一个字符串变成另一个的最少次数。它不包含“交换相邻字符算一次”这种额外操作。

用动态规划，定义 dp[i][j] 为把 word1 前 i 个字符变成 word2 前 j 个字符的最小成本。两个末尾字符相同，就沿用左上角；不同，就从删除、插入和替换三种选择中取最小成本，再加 1。空串对应首行和首列，分别初始化为目标或源前缀的长度。

完整表需要 O(mn) 时间和空间。只求距离时，每个状态只依赖上一行和当前行前一项，可以滚动保存两行，把额外空间降到 O(min(m, n) + 1)。

最长递增子序列要求保留原数组中的相对顺序，可以跳过元素，但相邻选中元素必须严格增大。通常先求长度；例如 [3, 5, 6, 2, 4, 7] 的答案是 4，可以选 [3, 5, 6, 7]。

有两种常用解法：

• 动态规划，O(n²)： dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。枚举前面的 j，若 nums[j] < nums[i]，就用 dp[j] + 1 更新。答案取整个 dp 的最大值。
• 最小结尾加二分，O(n log n)： tails[k] 保存已处理前缀中，长度为 k + 1 的递增子序列所能取得的最小结尾。依次处理每个值，用它替换第一个大于等于它的结尾；没有这样的结尾就追加。最后 tails 的长度就是答案。

两种方法都使用 O(n) 额外空间。tails 是不同长度的最优结尾记录，不一定是一条真实子序列。