刘毅

拓扑排序

May 26, 2019 • 算法 • Comment

在有向无环图（DAG，即 Directed Acyclic Graph）中，拓扑排序（Topological Sorting）是其顶点的线性排序，使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边，在排序中 $u$ 都在 $v$ 之前。

April 5, 2019 • 算法 • Comment

树状数组，也叫二叉索引树（Binary Indexed Tree，简称 BIT），由 Peter M. Fenwick 于 1994 年发表。其初衷是解决数据压缩里累积频率（Cumulative Frequency）的计算问题，现多用于动态地计算数组的区间和。

August 19, 2018 • 算法 • 2 Comments

并查集（Union-Find Set），也叫Disjoint Set，由Bernard A. Galler和Michael J. Fischer在1964年提出，它主要是用来解决动态连通性问题。

July 15, 2018 • 算法 • 1 Comment

Rabin-Karp算法（也可以叫Karp-Rabin算法），由Richard M. Karp和Michael O. Rabin在1987年发表，它也是用来解决多模式串匹配问题的。

July 8, 2018 • 算法 • Comment

前面已经分别介绍了两种平衡二叉树：AVL树和红黑树，先让我们来简单回顾下。