快速排序

简介 快速排序算法是对冒泡排序算法的一种改进。平均时间复杂度$O(nlogn)$,最坏时间复杂度$O(n^2)$。 快速排序的基本思想:每趟排序选择一个基准值pivot,使得小于pivot的元素和大于pivot的元素分隔于pivot两侧,即每一趟确定了一个元素的位置。然后对基准值两侧的区间进行递归,以达到整个序列有序。 ...

2021-04-25 · Lordash

Johnson

简介 Johnson算法是求解多源最短路的算法之一,核心操作是re-weight,适用于不包含负环(负权回路)的图。时间复杂度$O(nm+nmlogm)$。 ...

2020-08-12 · Lordash

Floyd-Warshall

简介 Floyd-Warshall算法是求解多源最短路的算法之一,核心思想是动态规划,适用于不包含负环(负权回路)的图。时间复杂度$O(n^{3})$,空间复杂度$O(n^{2})$。 ...

2020-08-12 · Lordash

Bellman-Ford

简介 Bellman-Ford算法是求解单源最短路的算法之一,适用于可包含负边权的有向和无向图,可以判断是否包含负环(注意,如果是包含负权回路则不存在最短路问题)。时间复杂度$O(nm)$。 ...

2020-08-12 · Lordash

Dijkstra

简介 Dijkstra算法是求解单源最短路的算法之一,核心思想是贪心,只适用于边权为正的无向和有向图。原复杂度$O(n^{2})$,优化后时间复杂度能到$O(mlog_{m})$。 ...

2020-08-12 · Lordash

字典树

简介 字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串)。优点是利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。 ...

2020-08-06 · Lordash

最小表示法

简介 最小表示法,求所有与某个字符串循环同构的字符串中,字典序最小的那个。比如说一个字符串lordash,它长度为7,也就是说最多有七种循环同构的方法。 ...

2020-08-04 · Lordash

Manacher

简介 Manacher’s Algorithm是用来查找一个字符串的最长回文子串的线性方法,由一个叫Manacher的人在1975年发明的。中文谐音“马拉车”算法。时间复杂度O(|S|)。 ...

2020-07-26 · Lordash

扩展KMP

简介 给定长度为n的文本串S和长度为m的模式串T,定义extend[i]为S[i…n-1]与T[0…m-1]的最长公共前缀长度,求extend[i]。当extend[x]==m时,则可知文本串S中包含模式串T,并且首位置为x,而这正是KMP算法处理的模式匹配问题。相较于KMP算法,扩展KMP算法能找到文本串S中所有模式串T的匹配,更一般地,可以知道文本串S中以每个字符开始的后缀与模式串T的最长公共前缀长度,时间复杂度O(n+m)。 ...

2020-07-26 · Lordash

KMP

简介 Knuth-Morris-Pratt字符串查找算法,简称为“KMP算法”,常用于在一个文本串S内查找一个模式串T的出现位置。这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。时间复杂度O(|S|+|T|)。 ...

2020-07-26 · Lordash

Fibonacci博弈

Fibonacci博弈 基本的斐波那契博弈(Fibonacci Game)描述如下: 有一堆数量多于一的物品,两人轮流取走物品,第一次至少取一个,但不能取完,从第二次开始每个人最少取一个,最多取对手上次取的两倍。 ...

2020-06-18 · Lordash

Wythoff博弈

Wythoff博弈 基本的威佐夫博弈(Wythoff Game)描述如下: 有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,每次至少取一个,多者不限,最后取光者得胜。 ...

2020-06-17 · Lordash

Bash博弈

Bash博奕 基本的巴什博弈(Bash Game)描述如下: 有一堆n个物品,两人轮流取走物品,每次至少取一个,最多取m个,最后取光者获胜。 博弈过程如下: 如果n<m,那么先手可以一次取完。先手必胜。 ...

2020-06-15 · Lordash

Nim博弈

Nim博弈 基本的尼姆博弈(Nim Game)描述如下: 有若干堆各若干个物品,两个人轮流从某一堆取任意多的物品,每次至少取一个,多者不限,最后取光者得胜。 博弈过程如下: ...

2020-06-14 · Lordash

SG函数

公平组合游戏 公平组合游戏(Impartial Combinatorial Games)简称ICG,大致定义如下: 游戏有2名选手 对于游戏任何一种可能的局面(position),合法的操作集合只取决于这个局面本身 选手轮流操作(move),且只能在合法操作集合中选择 在游戏出于某状态,当前选手合法操作集合为空时判负,游戏结束 查看解析 一个公平游戏可以抽象地用一个有向无环图来表示,这个图中每个点都对应一个状态,每条有向边代表从一个状态到另一个状态的合法操作。 ...

2020-06-08 · Lordash