算法进阶 · 小纸条

用哈希比较两个字符串是否相等，时间大约是多少？

逐字符计算哈希的递推式是什么样？

取子串哈希的思想和哪种预处理技巧类似？

为降低哈希误判概率，常用什么办法？

“统计有多少单词以 'ab' 开头”，用哪种工具最合适？

Floyd 求的是单源最短路还是任意两点最短路？

Floyd 三重循环里，代表“中转点”的循环变量放在第几层？

Floyd 中把 k 放在内层循环会有什么问题？

n 个点的图，Bellman-Ford 最多需要松弛几轮？

SPFA 相比朴素 Bellman-Ford 优化了什么？

inq[] 数组在 SPFA 里起什么作用？

SPFA 中怎样的迹象说明图里有负环？

Prim 每一步选择怎样的一条边？

Prim 里 dis[v] 表示的是什么？

边很少的稀疏图，一般更适合用哪种算法？

欧拉路要求每条边经过几次？

无向图能一笔画成回路，奇度点应有几个？

欧拉回路里，每个点的度数为什么必须是偶数？

二分图中，同一组内的两个点之间会有边吗？

染色时发现相邻两点同色，说明这个图怎样？

一个“匹配”里，同一个点最多被几条选中的边使用？

若 u 本身就是 v 的祖先，那么 LCA(u,v) 是谁？

up[u][k] 表示 u 向上跳多少步的祖先？

树上 u、v 距离公式里，为什么 dep[LCA] 要乘 2 再减？

“求图中任意两点间最短路”，点数只有几百，用哪个算法最省事？

Kahn 算法一开始把哪些点入队？

DAG 上 DP 一般要按什么顺序处理结点？

为什么最长路问题一般要求图是 DAG（无环）？

DAG 路径计数里，起点的 cnt 初值设为多少？

给“课程先修安排”和“树上两点距离”各选一个最合适的算法。