Hwcoder 算法笔记体系读书笔记

数组题通常把暴力枚举的两层循环压成“当前元素 + 已见信息”。两数之和用哈希保存 complement，最长连续序列用集合跳过非起点，前缀和把区间和转成两个端点差，差分把区间加法转成边界事件。双指针和滑动窗口的本质是维护一个满足条件的连续区间。

关键判断：如果目标是“区间和/次数/余数”，优先想前缀；如果是“最长/最短连续子数组”，先问窗口条件是否可随右端点单调变化；如果是“三数/接雨水/盛水容器”，先找排序或左右边界上的单调性。

位运算题的核心是把整数看成 32 或 64 个独立维度。经典技巧包括 \(n & (n-1)\) 消掉最低位 1、异或的自反消元、按位统计贡献、用 mask 表示集合状态。很多看似数组题的“只出现一次”问题，本质都是利用异或或按位计数恢复信息。

关键判断：如果题目出现“每个数出现 k 次，只有一个例外”“汉明距离总和”“最小 XOR”“子数组按位与/或”，应优先按 bit 位拆贡献，而不是在整数空间里硬模拟。

线段树维护区间聚合，适合区间查询和修改；树状数组更轻，适合前缀型可逆聚合；并查集维护动态连通分量，适合把“是否同组”压成根节点关系。读这组笔记时，应把每种结构的维护对象说清楚，而不是背实现长度。

关键判断：如果查询是区间最大值、区间和、动态更新，考虑线段树或 BIT；如果题目问连通性、等价关系、合并集合，考虑并查集；如果权值关系带比例，根节点路径上还要维护额外权重。

二分查找不是模板题，而是证明答案空间存在单调谓词。旋转数组、二维矩阵、峰值、平方根都在考边界语义；二分答案则把“能不能做到 x”变成判定函数。分治部分包括最大子数组、快速选择、归并统计逆序对，核心是把全局目标拆成左右子问题和跨边界信息。

关键判断：当题目要求最小最大值、最大最小值、满足条件的临界点，并且检查某个候选值可在 \(O(n)\) 或 \(O(n\log n)\) 完成，二分答案通常成立。

一维 DP 负责线性序列和状态机；二维 DP 负责矩阵、字符串匹配、背包；复杂 DP 覆盖树形、区间、状压和数位。DP 的真正难点不是公式，而是状态是否足够且不过度。状态定义错了，后面的转移再漂亮也没用。

关键判断：看到“方案数、最大/最小代价、可行性、编辑距离、背包容量、买卖股票状态、树上选或不选”时，先写状态语义，再写转移来源，最后决定遍历顺序和初始化。

图论笔记覆盖图遍历、矩阵图、拓扑排序、最短路、最小生成树和连通性。BFS/DFS 的差异不是递归和队列，而是搜索层次和状态回溯；拓扑排序维护入度为 0 的可执行节点；最短路维护已知最优距离；矩阵图则经常把坐标编码成节点。

关键判断：如果每条边权相等，用 BFS；非负边权用 Dijkstra；有依赖关系用拓扑；要连通性和合并用并查集；要“从多个源同时扩散”，多源 BFS 常常比逐点 BFS 更稳。

贪心专题包括扫描贪心、置换环、单调队列和排序贪心。贪心不是“看起来选最大/最小”，而是需要交换论证、区间支配关系或单调不变量。比如跳跃游戏维护当前最远可达，划分字母区间维护字符最后出现位置，任务调度器维护频次约束。

关键判断：如果局部选择能被证明支配其他选择，或者排序后只需维护一个最优边界，贪心可能成立；如果选择会影响多个未来状态且不能压缩，通常要回到 DP。

链表题覆盖扫描、合并、反转、双指针定位和缓存模拟。链表的难点不是算法思想，而是指针顺序：反转时先保存 next，删除时维护 prev，区间反转时处理 dummy 和尾连接。LRU/LFU 则把链表和哈希表组合起来实现 \(O(1)\) 访问和淘汰。

关键判断：删除头节点、反转头段、k 组翻转、环入口、相交点都应先放 dummy 或快慢指针框架，避免在头节点边界上写一堆特判。

数学专题重点是乘法原理、组合数、素数筛、逆元、中位数不等式和拒绝采样。很多“所有子数组/子序列贡献之和”不能枚举对象，只能枚举元素，计算它作为最大值、最小值、唯一字符或边界的出现次数。

关键判断：如果题目要求所有子数组的某个统计量总和，优先问“每个元素会被统计多少次”；如果涉及取模除法，需要逆元；如果是绝对值距离和，先考虑中位数最优性。

搜索回溯用于返回所有排列、组合、子集和括号生成；剪枝用于 N 皇后、删除无效括号等巨大搜索空间。回溯和普通 DFS 的差异在于状态会被修改并恢复。去重题的关键不是用不用 set，而是排序后在同层跳过重复分支。

关键判断：如果输出所有方案，指数复杂度通常不可避免，重点是剪枝；如果只求最短步数，BFS 往往更合适；如果有启发式下界，可考虑 A* 或 IDA*。

栈队列专题覆盖模拟、括号配对、表达式和单调栈。单调栈维护的是还没找到右侧更大/更小边界的元素，适用于每日温度、柱状图最大矩形、子数组最小值之和。单调队列则维护滑动窗口内候选最优值。

关键判断：如果每个元素要找左/右第一个更大或更小，单调栈；如果窗口移动中要维护最大/最小，单调队列；如果存在嵌套结构和成对抵消，普通栈通常够用。

字符串专题包括打印输出、KMP、Trie 和字符串哈希。树专题包括前中后序、层序、属性计算、路径问题和 LCA。字符串问题常通过前缀函数、字典树或 rolling hash 维护重复结构；树问题天然递归，常见套路是自底向上返回子树信息。

关键判断：字符串匹配优先问是否需要线性匹配、前缀共享或快速比较子串；树题优先问当前节点需要从左右子树拿什么信息，以及返回给父节点的值和全局答案是否相同。

这篇的主线是从 \(\operatorname{softmax}(QK^\top/\sqrt{d_k})V\) 出发，逐步加入多头拆分、causal mask、KV cache 和 K/V head 共享。真正的考点是每一步的张量形状：(batch, heads, seq, head_dim) 如何拆、如何转置、如何合并，mask 如何广播到 score 矩阵。

复习重点：decode 阶段 q_len 常为 1，而 k_len 是历史长度加当前 token；MHA 的 KV cache 成本随 head 数增长，MQA/GQA 通过共享 K/V 降低 cache 压力。

LayerNorm 在特征维度归一化，BatchNorm 在 batch 统计上归一化，RMSNorm 去掉均值中心化只保留均方根尺度。Dropout 需要区分训练和推理路径，梯度累积需要把多个 micro-batch 的梯度等价到一个大 batch 更新。

复习重点：归一化题必须先说清楚统计轴；梯度累积题必须说明 loss 是否除以 accumulation steps，否则有效学习率会被放大。

Transformer 手写不只是把 Attention 和 FFN 拼起来，还要处理 token embedding、position embedding、RoPE、残差、归一化、encoder self-attention、decoder causal self-attention 和 cross-attention。Encoder 和 Decoder 的差异主要在 mask 和是否关注 encoder 输出。

复习重点：RoPE 不是简单加位置向量，而是对 Q/K 的成对维度做旋转；残差路径和 LayerNorm 的位置会影响 pre-norm/post-norm 稳定性。

这篇把 MSE、CE、BCE、KL、Focal，Sigmoid、Tanh、ReLU、GeLU、SwiGLU、Softmax，以及 PPL、ROUGE、BLEU 放在一起。读法是把每个函数拆成输入范围、输出语义、梯度特性和数值稳定实现。

复习重点：Softmax/CE 要用 log-sum-exp 稳定化；KL 要说明方向；Focal loss 通过降低易分类样本权重处理类别不平衡；PPL 本质是平均负对数似然的指数形式。

这篇规模相对小，但适合作为从传统 ML 过渡到深度学习的桥。线性回归对应平方误差和解析/梯度解；逻辑回归对应 sigmoid 和二分类 CE；Softmax 回归对应多分类 CE；SGD 则连接到小批量优化和反向传播。

复习重点：不要只写 forward，要能写出 loss 对 logits、权重和 bias 的梯度方向；同时能解释 L2 正则如何影响权重更新。

RLHF 篇把优势估计、PPO policy/value loss、DPO loss、GRPO loss、reward 归一化和无偏 KL 放在一起。它适合放在最后读，因为它需要同时理解概率、梯度、序列级 reward 和 reference model 约束。

复习重点：GAE 是在 bias 和 variance 间折中；PPO clipping 限制策略更新幅度；DPO 把偏好对转成 log-ratio 分类目标；GRPO 通过组内相对优势减少 critic 依赖。