文章
KMP 与字符串哈希:两种字符串匹配优化
深入讲解 KMP 的 next 数组、失配跳转和字符串哈希的窗口摘要、取模与冲突处理。
NOTES / THINKING IN PUBLIC
记录技术实践,也记录判断如何形成、结论在什么条件下成立。
深入讲解 KMP 的 next 数组、失配跳转和字符串哈希的窗口摘要、取模与冲突处理。
用区间长度枚举和 bitmask 集合状态理解进阶 DP,说明状态数量、依赖顺序和规模边界。
从位数组和多哈希理解假阳性,推导容量参数,并分析删除限制与缓存穿透落地。
系统整理 0-1 背包、完全背包、多重背包、分组背包和方案数问题,重点区分遍历顺序。
理解用受控误差换取空间效率的共同思想,并比较 Bloom、Count-Min Sketch 与 HyperLogLog。
区分最短路和最小生成树,用 Prim 与 Kruskal 理解无向连通加权图里的最小连接成本。
手写两种图存储方式和 BFS,讨论重复边、权重、访问标记与 API 边界。
按无权、非负权、负权和多源查询选择最短路算法,并说明工程里权重建模的重要性。
建立有向、无向、加权、稀疏与稠密图的建模方式,并比较邻接矩阵和邻接表。
从无向图判环、账户合并、岛屿数量和等式约束理解并查集的算法应用边界。
使用父数组、路径压缩和按大小合并高效维护动态连通关系,并明确删除与路径查询边界。
从前序、中序、后序、层序遍历进入高度、直径、路径、LCA 和树形 DP 的状态设计。