文章
大厂笔试模式识别与组合题决策树
用约束、状态、不变量和复杂度识别原题、同构题与多算法组合题,减少错误套模板。
专题 算法与笔试训练 第 6 篇 / 共 8 篇
本文完整同步自个人求职工作区,更新于 2026-08-31。源文件及后续更新托管在 GitHub 仓库 llm-algo-job-notes。
目标:从“背关键词套模板”升级为“形式化题目、写最小充分状态、按复杂度筛选、用反例验伪”。本篇是 Hot100 模板 与 大厂超纲模板 之间的桥梁。
1. 先判断 LeetCode 映射等级
| 等级 | 判定 | 可以迁移什么 | 例子 |
|---|---|---|---|
| 原题级 | 目标、状态、转移几乎一致 | 思路和代码结构 | 拼多多面试 LIS → LC 300 |
| 同构 | 故事或数据变了,状态与转移一致 | 算法和证明,重写 I/O | 字节区间翻转增量 → LC 53;拼多多站距 → LC 1552 |
| 技术部件 | 只复用一个子结构 | 局部模板 | 动态统计 → LC 307/Fenwick;离线连通 → LC 1697/DSU |
| 组合题 | 两个以上阶段或算法流水线 | 分阶段模板,不能整题照搬 | 前缀和 + 二分 + 分治;逆序事件 + DSU |
| 无精确映射 | 复杂规则、模型/矩阵、特殊构造 | 状态建模、数值与工程纪律 | Attention、Viterbi、IRLS、双陆棋模拟 |
只有前两级适合“想起某道 LC 后直接迁移”。后三类必须重新证明状态、边界和复杂度。
2. 拿到题先写这张草稿
在代码前用 2–3 分钟写:
对象:数组 / 图 / 事件 / 矩阵 / 状态机?
操作:一次操作改变哪些量?顺序、同步更新、并列规则是否重要?
目标:判定 / 计数 / 最优 / 构造 / 输出全部方案?
约束:n, m, q, 值域, 边权, 负数, 测试组总和, 精度?
状态:决定未来所需的最少信息是什么?
不变量:循环/窗口/组件/阶段结束后始终成立什么?
暴力:最直接做法与复杂度?小数据能否先得部分分?
如果“相同位置”因为剩余步数、钥匙、mask、方向或轮次不同而影响未来,它们就是不同状态,visited 也必须按完整状态记录。
3. 约束先行的决策树
拿到题
│
├─ A. 输出所有具体方案?
│ ├─ 是 → 回溯;先估分支数
│ └─ 只计数/最优 → 找重叠子问题,优先 DP
│
├─ B. 子集选择?
│ ├─ n≤20 → 回溯/状压
│ ├─ n≈35~45 → Meet-in-the-middle
│ └─ 有容量/价值 → 背包
│
├─ C. 连续子数组/字符串?
│ ├─ 长度固定 → 滚动和/固定窗口
│ ├─ 右扩只会变坏、左缩只会变好 → 可伸缩滑窗
│ ├─ 和等于 K / 区间和计数 → 前缀和 + 哈希
│ ├─ 最大连续和 → Kadane
│ └─ 前缀极值约束 → 单调队列
│
├─ D. 图/网格?
│ ├─ 静态连通/只加边 → DFS/BFS/DSU
│ ├─ 删边且允许离线 → 逆序 DSU
│ ├─ 边权全 1 / 0-1 / 非负 / 限步或负权
│ │ → BFS / 0-1 BFS / Dijkstra / 分层 Bellman-Ford
│ ├─ 依赖且无环 → 拓扑 + DAG DP
│ ├─ 连通全部点最小代价 → MST
│ └─ 树上聚合/最优 → 树形 DP
│
├─ E. 区间查询或在线更新?
│ ├─ 静态查询 → 一维/二维前缀
│ ├─ 单点更新 + 前缀/区间和 → Fenwick
│ └─ 区间更新或复杂合并 → 线段树
│
├─ F. 每点恰有一个后继?
│ └─ 函数图:入度剥离找环;大步跳转用倍增
│
├─ G. 规则很多、算法名不明显?
│ └─ 状态机:事件阶段 + 优先级 + 同步/异步 + 不变量
│
└─ H. JSON/矩阵/概率模型/优化器?
└─ 转 [ML/AI Coding 补丁](/blog/ml-ai-coding-patch/),不要强行映射 Hot100
复杂度看的是总状态量,不是只看一个 n:还要算 n*m、n*q、2^n、边数、值域和所有测试组之和。
4. 高频误判与否证问题
| 看到什么 | 容易误判 | 先问什么 |
|---|---|---|
| “连续 + 最长/最短” | 一律滑窗 | 合法性是否有单调性?负数会不会让窗口重新合法? |
| “存在/计数” | 一律哈希 | key 能否直接表示等价类/补数?还是路径/方案 DP? |
| “最少步数” | 一律 BFS | 边权是否为 1?位置之外还有资源/步数状态吗? |
| “Top-K” | 一律堆 | 静态可排序?只求第 K 可 quickselect?动态排名需 Fenwick/有序结构? |
| “最优值” | 一律贪心 | 是否有交换论证、领先性或单调不变量? |
| “矩阵” | 一律网格 DFS | 是连通、区域和、坐标变换,还是矩阵乘/Attention? |
| “图” | 一律 DSU/拓扑 | 问连通、距离、生成树、依赖、匹配还是树/DAG DP? |
| “和为 K” | 一律前缀和 | 元素非负且问最短/最长时,滑窗是否更直接? |
提交候选算法前做四问:
- 单调性真的成立吗?构造一个右扩后又变好的例子。
- 状态是否丢信息?相同索引但不同资源能否合并?
- 局部最优能证明全局最优吗?不能只说“看起来最优”。
- 能否用
n≤8的暴力程序随机对拍?贪心、构造、数据结构尤其应该对拍。
5. 组合题按“流水线”识别
| 流水线 | 题面信号 | 公开题型例子 |
|---|---|---|
| 变换 → 经典算法 | 对每个元素先做操作,再选区间/子集 | 数字翻转增量 → Kadane |
| 预处理 → 多查询 | 同一数组/矩阵回答大量区间问题 | 二维前缀和统计子矩阵 |
| 排序 → 贪心/DP | 原顺序不重要或可先固定一维顺序 | 车辆排序后求 LNDS |
| 前缀和 → 二分 → 分治 | 递归切割,需快速判断某段是否满足 | 携程等和递归切割 |
| 事件逆序 → DSU | 只有删边,在线难、倒放变加边 | 美团动态删边连通块 |
| 建图 → 拓扑/DP | 原题是约束关系,不直接给图 | 树上按大小定向形成 DAG |
| 状态扩维 → 最短路 | 同一位置的剩余资源不同 | 限中转次数航班、角色移动 |
| 坐标压缩 → Fenwick/线段树 | 值域大、动态排名/统计 | 淘天区间统计、实时榜单 |
识别组合题后,给每一阶段分别写输入、输出和复杂度。例如:
排序 O(n log n)
→ 坐标压缩 O(n log n)
→ q 次 Fenwick 更新/查询 O(q log n)
总复杂度 O((n+q) log n),而不是笼统写“用了树状数组”。
6. 进阶模式速查
| 模式 | 最小识别条件 | 模板入口 | 关键边界 |
|---|---|---|---|
| 固定窗口 | 长度恰为 k | fixed_window_sums | k=1/n,不是可伸缩滑窗 |
| 连通块编号 | 反复查询块大小/翻转后合并 | label_components | 全 0、全 1、重复邻块去重 |
| 含权逆序 DSU | 删边 + 查询组件 sum/max | offline_component_queries | 平行边、静态节点权、每边只删一次 |
| 动态区间和 | 单点赋值/增加 + 区间查询 | Fenwick / SegmentTreeSum | 0/1-based、半开区间 |
| 函数图跳跃 | 每点一个后继、问第 k 步 | FunctionalGraphJumps | 自环、k=0、超大 k |
| MST | 连接所有点且总边权最小 | kruskal_mst | 图不连通;构造题还需独立 validator |
| 最小权完美匹配 | 两组一一配对、总代价最小 | min_cost_assignment | 矩形方向、负权、并列最优 |
| 限步最短路 | 最多走 K 条边/中转 | cheapest_with_edge_limit | 同轮必须读旧 dist |
| MITM | n≈40 的子集优化 | min_abs_subset_sum_difference | 空子集、负数、左右二分 |
以上可执行实现位于 algorithm_exam_advanced.py。
差分约束不要混成一种
- 等式
x[v]-x[u]=w:建带权图传播势能,或使用带权 DSU;遇到已访问节点时检查是否矛盾。 - 不等式
x[v]≤x[u]+w:建边u→v(w),转成最短路可行性;加超级源并用 Bellman-Ford 检查负环。
MST 与生成树构造也不是一种
Kruskal 解决“总权最小”。若题目要求特定度数、颜色或最大度差,应采用:
- 写必要条件。
- 构造满足核心限制的骨架。
- 补到恰好
n-1条边。 - 用独立 validator 检查无自环、无重复、连通、无环及额外约束。
7. 一道题怎样算真正掌握
- 能写清映射等级,不把技术部件冒充原题。
- 能说出状态/不变量以及一个错误状态定义的反例。
- 能从约束推导复杂度,而不是先选模板再解释。
- 组合题能分阶段列出复杂度和接口。
- 24 小时后从空文件盲写,并用边界用例或随机暴力对拍。
原始文档:GitHub 源文件。