文章

大厂笔试模式识别与组合题决策树

用约束、状态、不变量和复杂度识别原题、同构题与多算法组合题,减少错误套模板。

2026年7月26日 更新于 2026年8月31日 约 6 分钟

专题 算法与笔试训练 第 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”一律前缀和元素非负且问最短/最长时,滑窗是否更直接?

提交候选算法前做四问:

  1. 单调性真的成立吗?构造一个右扩后又变好的例子。
  2. 状态是否丢信息?相同索引但不同资源能否合并?
  3. 局部最优能证明全局最优吗?不能只说“看起来最优”。
  4. 能否用 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. 进阶模式速查

模式最小识别条件模板入口关键边界
固定窗口长度恰为 kfixed_window_sumsk=1/n,不是可伸缩滑窗
连通块编号反复查询块大小/翻转后合并label_components全 0、全 1、重复邻块去重
含权逆序 DSU删边 + 查询组件 sum/maxoffline_component_queries平行边、静态节点权、每边只删一次
动态区间和单点赋值/增加 + 区间查询Fenwick / SegmentTreeSum0/1-based、半开区间
函数图跳跃每点一个后继、问第 k 步FunctionalGraphJumps自环、k=0、超大 k
MST连接所有点且总边权最小kruskal_mst图不连通;构造题还需独立 validator
最小权完美匹配两组一一配对、总代价最小min_cost_assignment矩形方向、负权、并列最优
限步最短路最多走 K 条边/中转cheapest_with_edge_limit同轮必须读旧 dist
MITMn≈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 解决“总权最小”。若题目要求特定度数、颜色或最大度差,应采用:

  1. 写必要条件。
  2. 构造满足核心限制的骨架。
  3. 补到恰好 n-1 条边。
  4. 用独立 validator 检查无自环、无重复、连通、无环及额外约束。

7. 一道题怎样算真正掌握

  • 能写清映射等级,不把技术部件冒充原题。
  • 能说出状态/不变量以及一个错误状态定义的反例。
  • 能从约束推导复杂度,而不是先选模板再解释。
  • 组合题能分阶段列出复杂度和接口。
  • 24 小时后从空文件盲写,并用边界用例或随机暴力对拍。

原始文档:GitHub 源文件。

本页目录