最短路算法
February 11, 2022
Dijkstra用于求没有负权边的单源最短路。
...快速求最大公约数gcd
February 9, 2022
快速求两个数的最大公约数(公因数)有两个办法：
- 更相减损法
- 辗转相除法
AC自动机
January 25, 2020
AC自动机用于解决下述问题及其同类问题:
...给定一系列模式串和一个文本串，判断有多少模式串出现在文本串中，给出数目和对应模式串的出现位置。
Trie树
January 24, 2020
Trie树可以:
- 压缩存储大量的字符串
- 快速找出具有相同前缀的字符串
- 快速按字典序对字符串进行排序
- …
错误检测-海(汉)明码
October 15, 2018
Hamming code，海明码，汉明码都是一个东西。它是一种编码方式，通常用在网络信息传输中，通过这种编码方式编码出来的二进制数据具有检测一位错误位的能力。
...克鲁斯卡尔算法
April 15, 2018
首先，克鲁斯卡尔算法是用来求最小生成树的。另一种求最小生成树的算法叫普林姆算法（Prim）。
...普林姆算法
April 15, 2018
普林姆算法也是用来求最小生成树的，与克鲁斯卡尔算法遍历边不同，普林姆遍历的是点。
普林姆算法同样基于贪心，以任意点为初始点，每次选取与已选点相连的边中权值最小的边，并把与这条边相连的点加入已选点集合。
并查集
April 15, 2018
使用并查集可以快速判断两个元素是否属于同一个集合。
...Fibonacci数的迭代算法
September 30, 2017
使用迭代算法求斐波那契数列，
时间复杂度O(n)，空间复杂度O(1)。
...快速幂算法
September 30, 2017
在c，c++语言中，并没有提供求幂的基本运算，通常我们需要自己写函数或者调用STL提供的函数。
一般情况下，我们写的求幂函数基本上都是循环累乘，时间复杂度为O(n)。虽说是线性的时间复杂度，但求幂运算作为基础运算，往往调用频繁，这时候即使是线性的时间复杂度也将变得难也接受。
利用快速幂可以快速计算底数的n次幂。其时间复杂度为 O(logn)
...