Cao Note

外观

高频算法题套路 ​

把力扣/牛客的常考题归类成十几个可套用的「套路」。目标：看到题先命中套路 → 背模板 → 改细节。每个套路给出识别特征、模板伪代码、代表题与刷题路线。

一、双指针 ​

1.1 快慢指针（同向） ​

  • 识别特征：链表求中点/倒数第 K 个、判环、找环入口；数组"原地去重/移动元素"。
  • 模板：
python
# 链表判环：快指针每次 2 步，慢指针 1 步，相遇则有环
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True      # 找入口：再让一个从头走，相遇点即环入口
return False

# 数组原地去重（已排序）：慢指针指向"已去重区末尾"
j = 0
for i in range(1, len(a)):
    if a[i] != a[j]:
        j += 1
        a[j] = a[i]
# 答案长度 = j + 1
# 链表判环：快指针每次 2 步，慢指针 1 步，相遇则有环
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True      # 找入口：再让一个从头走，相遇点即环入口
return False

# 数组原地去重（已排序）：慢指针指向"已去重区末尾"
j = 0
for i in range(1, len(a)):
    if a[i] != a[j]:
        j += 1
        a[j] = a[i]
# 答案长度 = j + 1
  • 代表题：LeetCode 141 环形链表、142 环形链表 II、876 链表中点、26 删除有序数组重复项、19 删除链表倒数第 N 个。

1.2 左右对撞指针 ​

  • 识别特征：有序数组上找两数之和等于目标、回文判断/回文子串扩展、接雨水/盛水容器、反转数组。
  • 模板：
python
# 有序数组两数之和 = target
lo, hi = 0, len(a) - 1
while lo < hi:
    s = a[lo] + a[hi]
    if s == target: return (lo, hi)
    if s < target: lo += 1      # 和小了 → 左指针右移
    else: hi -= 1               # 和大了 → 右指针左移
# 有序数组两数之和 = target
lo, hi = 0, len(a) - 1
while lo < hi:
    s = a[lo] + a[hi]
    if s == target: return (lo, hi)
    if s < target: lo += 1      # 和小了 → 左指针右移
    else: hi -= 1               # 和大了 → 右指针左移
  • 核心是单调性：指针按方向移动时，搜索空间单调收缩，保证不遗漏。
  • 代表题：LeetCode 167 两数之和 II、11 盛最多水的容器、125 验证回文串、15 三数之和（固定一个+对撞）。

二、滑动窗口 ​

2.1 识别特征 ​

  • 子串/子数组问题 + 关键词"最长/最短/恰好含/连续" + 窗口随右边界扩大、左边界收缩。
  • 数据规模提示：n 达 10⁵，O(n²) 必超时，滑动窗口把枚举起点降为 O(n)。

2.2 框架模板（可变窗口） ​

python
def sliding_window(s):
    from collections import Counter
    window = Counter()          # 或 dict 记录窗口内元素
    lo = 0
    ans = 0
    for hi in range(len(s)):            # 1. 右边界扩张
        window[s[hi]] += 1
        while 窗口不满足约束:            # 2. 收缩左边界直到满足
            window[s[lo]] -= 1
            lo += 1
        ans = max(ans, hi - lo + 1)     # 3. 窗口此刻满足条件，更新答案
    return ans
def sliding_window(s):
    from collections import Counter
    window = Counter()          # 或 dict 记录窗口内元素
    lo = 0
    ans = 0
    for hi in range(len(s)):            # 1. 右边界扩张
        window[s[hi]] += 1
        while 窗口不满足约束:            # 2. 收缩左边界直到满足
            window[s[lo]] -= 1
            lo += 1
        ans = max(ans, hi - lo + 1)     # 3. 窗口此刻满足条件，更新答案
    return ans
  • 口诀：右扩 → 不满足就左缩 → 缩到满足后记答案。
  • 时间复杂度 O(n)：左右指针各至多走一遍。

2.3 变体：固定窗口大小 vs 可变 ​

变体处理例子
固定长度 k每步先加右边再减左边，直接算大小为 k 的子数组最大平均值
可变最长while 缩到合法无重复字符的最长子串
可变最短合法时尽量收缩更新最小最小覆盖子串、最短超串
计数限制型窗口内最多 k 种/频次 ≤ k至多 K 个不同字符的最长子串
  • 代表题：LeetCode 3 无重复字符最长子串、76 最小覆盖子串、209 长度最小子数组、424 替换后最长重复字符。

三、前缀和与差分 ​

3.1 前缀和 ​

  • 识别特征：反复求子数组/子区间和、子数组和为 k 的个数、二维子矩阵和。
  • 一维：pre[i+1] = pre[i] + a[i]，则 sum(l..r) = pre[r+1] - pre[l]，O(1) 查询。
python
def subarray_sum(nums, k):          # 和为 k 的子数组个数
    pre = {0: 1}                    # 前缀和 → 出现次数
    s = ans = 0
    for x in nums:
        s += x
        ans += pre.get(s - k, 0)    # 存在 pre[j] = s-k 使 (j..i] 和为 k
        pre[s] = pre.get(s, 0) + 1
    return ans
def subarray_sum(nums, k):          # 和为 k 的子数组个数
    pre = {0: 1}                    # 前缀和 → 出现次数
    s = ans = 0
    for x in nums:
        s += x
        ans += pre.get(s - k, 0)    # 存在 pre[j] = s-k 使 (j..i] 和为 k
        pre[s] = pre.get(s, 0) + 1
    return ans
  • 二维前缀和：pre[i][j] = a + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]（容斥）。
  • 代表题：LeetCode 560 和为 K 的子数组、303/304 区域和检索、525 连续数组。

3.2 差分 ​

  • 识别特征：对区间反复做「整体加/减」，最后只要一次结果（"多次区间更新 + 最后查询"）。
  • 思想：diff[l] += v, diff[r+1] -= v，最后前缀和还原原数组，把区间操作变 O(1)。
python
def apply(diff, l, r, v):
    diff[l] += v
    diff[r + 1] -= v
def apply(diff, l, r, v):
    diff[l] += v
    diff[r + 1] -= v
  • 代表题：LeetCode 370 区间加法、1109 航班预订统计、差分典型"打气球"。

3.3 识别小结 ​

关键词用哪个
子数组和 / 区间和频繁查询前缀和
和为 k / 差为 k 的连续段计数前缀和 + 哈希表
多次区间加值后输出数组差分
子矩阵和二维前缀和

四、单调栈 ​

4.1 识别特征 ​

  • 求数组中每个元素「左边/右边第一个比它大/小」的位置或距离。
  • 暴力是 O(n²)；单调栈让每个元素至多入栈出栈一次 → O(n)。

4.2 模板（下一个更大元素） ​

python
def next_greater(nums):            # 返回每个元素右边第一个更大元素下标，没有则 -1
    stack, res = [], [-1] * len(nums)
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:   # 栈顶被 x 顶掉 → x 是它的答案
            res[stack.pop()] = i
        stack.append(i)
    return res
def next_greater(nums):            # 返回每个元素右边第一个更大元素下标，没有则 -1
    stack, res = [], [-1] * len(nums)
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:   # 栈顶被 x 顶掉 → x 是它的答案
            res[stack.pop()] = i
        stack.append(i)
    return res
  • 技巧：找「右边更大」从左往右扫；找「左边更大」从右往左扫（或入栈时栈内即左侧信息）。
  • 栈内维护单调递减/递增的下标（比较的是数组值），下标用来算距离。
  • 代表题：LeetCode 496 下一个更大元素 I、739 每日温度、84 柱状图最大矩形、42 接雨水。

4.3 延伸：单调队列（滑动窗口最值） ​

  • 窗口滑过数组求每个窗口最大/最小值：用 deque 维护窗口内值单调递减，队首即最大。
  • 与单调栈区别：单调队列两端都操作（窗口要淘汰过期元素）；复杂度 O(n)。
  • 代表题：LeetCode 239 滑动窗口最大值。

五、BFS 层级框架 ​

5.1 识别特征 ​

  • 关键词：最短/最少步数、逐层扩散、状态按层推进（迷宫最短路、单词接龙、打开转盘锁）。
  • 网格四/八方向扩散、二叉树层序遍历也是 BFS。

5.2 模板（记录层级） ​

python
from collections import deque

def bfs(start, is_target, neighbors):
    q = deque([start])
    seen = {start}
    step = 0
    while q:
        for _ in range(len(q)):        # 一次处理一整层
            cur = q.popleft()
            if is_target(cur):
                return step
            for nxt in neighbors(cur):
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        step += 1
    return -1                          # 不可达
from collections import deque

def bfs(start, is_target, neighbors):
    q = deque([start])
    seen = {start}
    step = 0
    while q:
        for _ in range(len(q)):        # 一次处理一整层
            cur = q.popleft()
            if is_target(cur):
                return step
            for nxt in neighbors(cur):
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        step += 1
    return -1                          # 不可达
  • 三个要点：seen 在入队时就标记（防止重复入队）；层数在每层结束时 +1；"最少步数" = 首次命中目标的层数。

5.3 双向 BFS（进阶） ​

  • 起点终点都已知时，从两头交替 BFS，相遇即答案，规模从 b^d 降到约 2·b^(d/2)。
  • 适用：单词接龙等状态空间大的题；实现用两个集合交替扩展小的一侧。
  • 代表题：LeetCode 102 层序、127 单词接龙、752 打开转盘锁、200 岛屿数量（连通块 BFS/DFS 均可）。

六、DFS 回溯模板 ​

6.1 识别特征 ​

  • 求所有方案/路径（全排列、组合、子集、N 皇后、复原 IP、岛屿中的路径型）。
  • 网格里"从某点能走到哪些点/路径和"用 DFS；问"最少几步"才用 BFS。

6.2 模板 ​

python
def dfs(路径, 选择列表):
    if 结束条件:
        记录结果                    # 注意深拷贝 path[:]
        return
    for 选择 in 选择列表:
        剪枝条件: continue
        做选择（标记 visited / 加入 path / 累加和）
        dfs(路径更新, 选择列表更新)
        撤销选择
def dfs(路径, 选择列表):
    if 结束条件:
        记录结果                    # 注意深拷贝 path[:]
        return
    for 选择 in 选择列表:
        剪枝条件: continue
        做选择（标记 visited / 加入 path / 累加和）
        dfs(路径更新, 选择列表更新)
        撤销选择
  • 网格 DFS（岛屿）常配合原地置 '0'/'#' 代替 visited，省空间。
  • 与树 DFS 区别：树天然无环不用 visited，图/网格/排列必须去重。
  • 代表题：LeetCode 46 全排列、78 子集、79 单词搜索、200 岛屿数量、22 括号生成。
  • 与回溯专题的完整拆解见动态规划与回溯。

七、位运算技巧 ​

7.1 常用操作表 ​

操作写法用途
取最低位的 1x & (-x)树状数组、lowbit
去掉最低位的 1x & (x - 1)数 1 的个数
判断 2 的幂x > 0 and x & (x-1) == 0
异或a ^ a = 0，a ^ 0 = a找唯一不重复元素
交换a ^= b; b ^= a; a ^= b面试加分项
取第 k 位(x >> k) & 1状态压缩
置第 k 位为 1`x= (1 << k)`

7.2 常见题 ​

  • 找只出现一次的数字（其余成对）：全部异或 → LeetCode 136。
  • 只出现一次的两个数字：全员异或得到 a^b，取 lowbit 分组再异或 → LeetCode 260。
  • 子集枚举/状态压缩：for mask in range(1<<n) 配合 (mask>>i)&1 判选。
  • 数 1 个数：循环 x &= x-1 计数（O(个数)）→ LeetCode 191、338。

八、字符串处理 ​

8.1 常见子问题 ​

  • 反转/回文：双指针判回文；中心扩展求回文子串个数（O(n²)）；Manacher 是进阶。
  • 子串匹配：KMP（next 数组）用于"主串里找模式串"；笔试可先用内建 index/str.find。
  • 字符计数：只含小写字母时可用长度 26 数组当哈希表，比 dict 更快。
  • 字符串切分还原：复原 IP、单词拆分 → DFS 或 DP。

8.2 哈希/计数套路 ​

  • 判断两个词是否异位词：频次数组相同；滑动窗口里维护频次差即可 O(1) 更新比较。
  • 最长无重复子串、最小覆盖子串都是"计数 + 滑动窗口"（见第二节）。
  • 整数与字符串互转注意符号、溢出、前导空格（atoi 题要按题面边界处理）。
  • 代表题：LeetCode 344 反转字符串、5 最长回文子串、49 字母异位词分组、242 有效的字母异位词、14 最长公共前缀。

九、TopK / 堆套路 ​

9.1 识别特征 ​

  • 前 K 大/小、第 K 大/小、数据流里的最值、合并 K 个有序链表。
  • 数据规模提示：不能全排序（n 巨大）或数据是流式输入 → 堆。

9.2 模板与题 ​

python
import heapq

def top_k_frequent(nums, k):        # 前 K 个高频元素
    from collections import Counter
    cnt = Counter(nums)
    # 维护大小为 k 的小顶堆：(频次, 值)，堆顶是最小的频次
    return [x for _, x in heapq.nlargest(k, [(v, k_) for k_, v in cnt.items()])]
import heapq

def top_k_frequent(nums, k):        # 前 K 个高频元素
    from collections import Counter
    cnt = Counter(nums)
    # 维护大小为 k 的小顶堆：(频次, 值)，堆顶是最小的频次
    return [x for _, x in heapq.nlargest(k, [(v, k_) for k_, v in cnt.items()])]
  • 求前 K 大 → 维护大小为 K 的小顶堆（比堆顶大就替换）；求前 K 小 → 大顶堆。
  • 中位数流：大顶堆存小半 + 小顶堆存大半，平衡两堆大小。
  • 合并 K 个有序链表：全部头节点入堆，弹出即接、再压入该链表下一个。
  • 代表题：LeetCode 215 数组第 K 大、347 前 K 高频元素、23 合并 K 个升序链表、295 数据流中位数。

十、其他高频套路速览 ​

10.1 排序 + 扫描 ​

  • 会议安排/区间合并：先按起点排序再线性扫描合并 → 重叠区间合并、插入区间、最多不重叠区间。
  • 代表题：LeetCode 56 合并区间、435 无重叠区间、252 会议室。

10.2 哈希表空间换时间 ​

  • 两数之和 / 三数之和、判断存在、计数 —— 凡"查历史"用哈希。
  • 链表深拷贝、复制带随机指针的链表：先建"老节点 → 新节点"映射。
  • 代表题：LeetCode 1 两数之和、138 复制带随机指针的链表。

10.3 区间与顺序类杂项 ​

  • 跳跃游戏类：维护"当前能到的最远下标"，一次遍历。
  • 括号匹配/表达式求值：栈。
  • 单调函数求最值：答案二分（见排序与查找 11.4）。

十一、刷题路线建议 ​

11.1 分组 A（第 1~2 周）：数组与哈希 ​

  • 题型：数组遍历、双指针、哈希表、滑动窗口入门。
  • 题单：LeetCode 1、26、167、3、560。
  • 目标：熟练 O(n) 遍历思路，建立"空间换时间"直觉。

11.2 分组 B（第 3~4 周）：链表与二叉树 ​

  • 题型：链表反转/环/合并；二叉树递归遍历与层序。
  • 题单：LeetCode 206、141、21、102、104、226（翻转二叉树）。
  • 目标：递归思维过关，能把二叉树题当模板背。

11.3 分组 C（第 5~6 周）：二分、排序、堆 ​

  • 题型：二分模板与变体、TopK、堆。
  • 题单：LeetCode 704、34（左右边界）、33（旋转数组）、215、347。
  • 目标：任何"有序/部分有序/最值"题都能联想到二分或堆。

11.4 分组 D（第 7~9 周）：回溯与动态规划 ​

  • 题型：全排列/组合/子集 → 爬楼梯/背包/LIS → 编辑距离。
  • 题单：LeetCode 46、78、22、70、198（打家劫舍）、300、72。
  • 目标：背熟回溯模板与 DP 五步法，做到"识别即套"。

11.5 分组 E（第 10~12 周）：图与综合 ​

  • 题型：岛屿类 BFS/DFS、拓扑排序、Dijkstra、并查集。
  • 题单：LeetCode 200、994（腐烂橘子）、207、994 或 542（01 矩阵）、547（省份数量）。
  • 目标：覆盖面试冷门区，保底"会写模板、能讲复杂度"。

11.6 节奏与复盘建议 ​

  • 每天 2~3 题，一题多解（暴力 → 优化）优先于贪多。
  • 每道题打标签：套路名 + 复杂度，错题单独建清单，每周重刷一遍错题。
  • 面试前两周：只看套路清单和错题标签，不再开新题；模拟口头讲思路（识别特征 + 模板 + 复杂度）。

Copyright © 2024-present xiaocao