文章
网络流入门:最大流、增广路与最小割
从容量约束、残量网络和增广路建立最大流直觉,并说明最大流最小割定理的含义。
NOTES / THINKING IN PUBLIC
记录技术实践,也记录判断如何形成、结论在什么条件下成立。
从容量约束、残量网络和增广路建立最大流直觉,并说明最大流最小割定理的含义。
用 dfn、low 和栈理解 Tarjan 算法,说明强连通分量如何帮助有向图缩点成 DAG。
讲解二分图染色、最大匹配、匈牙利算法直觉,以及任务分配、资源匹配等工程场景。
讲清 pos、tight、started 和业务状态,使用记忆化搜索统计范围内满足条件的数字数量。
通过树上打家劫舍、树的直径和节点状态合并,理解树形 DP 为什么通常使用后序遍历。
拆解打家劫舍、最大子数组和、最长递增子序列和最长公共子序列,训练 DP 状态定义。
理解 Z 函数如何描述后缀与前缀匹配,后缀数组如何排序所有后缀并处理重复子串和 LCP。
通过分隔符、回文半径、中心和最右边界理解 Manacher,说明它如何复用镜像信息减少重复扩展。
从敏感词检测场景出发,讲清 AC 自动机如何用 Trie 和 fail 指针把多模式匹配合并成一次扫描。
把 AC 自动机、Manacher、Z 函数和后缀数组放到一张路线图里,按问题类型选择字符串算法。
从普通取模的问题讲到哈希环、虚拟节点、节点扩缩容和热点 key,理解一致性哈希的工程边界。
从缓存淘汰需求出发,讲清 LRU 为什么需要 HashMap 加双向链表,以及 get、put、淘汰的 O(1) 实现。