English

纯 JavaScript 实现的数据结构和算法，主要是方便用于比赛、教学和白板，尽可能缓解 JavaScript 在竞赛上的劣势，特点：

• 拷来即用。支持所有 LTS/* Node.js 且零依赖。
• 容易更改。采用简化的实现，尽量少的抽象层级。
• 支持 npm。加一句 require，即可写出可以工作的代码。

支持在 LeetCode 页面提取、执行、判定用例的 Tampermonkey 脚本： https://greasyfork.org/zh-CN/scripts/402276-leetcode-helper-for-javascript

索引

TypeScript JavaScript Test Cases

补充 JavaScript 中一些针对数组的操作。比如 JavaScript 缺少 swap，不能对区间进行 reverse。

swap(arr: any[], lhs: number, rhs: number)：在数组 arr 里替换 lhs 和 rhs 的值。

shuffle(arr: any[])：用 Fisher-Yates 方法随机打乱数组。

let arr = [1, 2, 3]
shuffle(arr)
console.log(arr) // [1, 3, 2]

reverse(arr: any[], begin = 0, end = arr.length)：反转数组 arr 里的 [begin, end) 之间的元素。

let arr = [1, 2, 3, 4, 5]
reverse(arr, 1)
console.log(arr) // [1, 5, 4, 3, 2]

sort(arr: any[], begin = 0, end = arr.length, compare = (l, r) => l - r)：使用快排堆数组进行原址排序（不稳定），支持对一个区间进行排序，以及自定义 compare 方法。

let arr = [1, 3, 2]
sort(arr) // [1, 2, 3]
sort(arr, (l, r) => r - l) // [3, 2, 1]

createGraph(edges)：从边 [T, T, number] 的数组创建有表示向图的二维映射。可用于 dijkstra 算法。

const G = createGraph([
    [0, 1, 10],
    [1, 0, 30],
    [1, 2, 50]
])
G.get(0) // Map(1) { 1 => 10 }
G.get(1) // Map(2) { 0 => 30, 2 => 50 }

dijkstra(source, G): 单源最短路径算法。G 为二维映射，G.get(u).get(v) 表示有向图中边 u 到 v 的权。source 和 G 的键可以是任意基本类型比如数字、字符串等。返回一个 dist: Map<T, number>，dist[u] 表示 source 到 u 的最短路径长度。

const G = new Map()
G.set(0, new Map([[1, 10]]))
G.set(1, new Map([[0, 30], [2, 50]]))

dijkstra(0, G) // Map(3) { 0 => 0, 1 => 10, 2 => 60 }

可以借助于 createGraph()，上述代码等价于：

const G = new createGraph([
    [0, 1, 10],
    [1, 0, 30],
    [1, 2, 50],
])

dijkstra(0, G) // Map(3) { 0 => 0, 1 => 10, 2 => 60 }

nextPermutation(arr)：重组为下一个字典序排列。如果可以得到更大的排列，就完成排列并返回 true。如果无法得到更大的排列，就重排为第一个排列（所有元素都是升序）并返回 false。

prevPermutation(arr)：重组为上一个字典序排列。如果可以得到更小的排列，就完成排列并返回 true。如果无法得到更小的排列，就重排为最后一个排列（所有元素都是降序）并返回 false。

TypeScript JavaScript Test Cases

kmp(str: string, pattern: string)：使用 KMP 方法在 str 中找到 pattern 的下标，如果不存在则返回 -1。

kmp('what a wonderful world', 'a wonderful') // returns 5

rabinkarp(str: string, pattern: string)：使用 Rabin-Karp 方法在 str 中找到 pattern 的下标，如果不存在则返回 -1。

rabinkarp('what a wonderful world', 'a wonderful') // returns 5

TypeScript JavaScript Test Cases

new Queue(collection?: Iterable)：创建一个队列。

.size(): number：返回队列的大小。

.front()：返回第一个元素，为空时返回 undefined。

.back()：返回最后一个元素，为空时返回 undefined。

.shift()：移除并返回第一个元素，为空时返回 undefined。

.push(element: any)：在尾部添加一个元素。

.values()：返回从第一个元素到最后一个元素的 ES6 迭代器。

TypeScript JavaScript Test Cases

new Deque(collection?: Iterable)：创建一个双向队列。

.size(): number：返回双向队列的大小。

.unshift(element: any)：在头部添加一个元素。

.front()：返回第一个元素，为空时返回 undefined。

.back()：返回最后一个元素，为空时返回 undefined。

.shift()：移除并返回第一个元素，为空时返回 undefined。

.push(element: any)：在尾部添加一个元素。

.pop()：移除并返回最后一个元素，为空时返回 undefined。

.values()：返回从第一个元素到最后一个元素的 ES6 迭代器。

let deque = new Deque([1, 2, 3])
deque.push(4)
deque.unshift(0)
deque.pop() // returns 4
deque.pop() // returns 3
deque.shift() // returns 0
for (let val of deque) {
  console.log(val) // outputs 1 and 2
}

TypeScript JavaScript Test Cases

new Heap(collection?: Iterable, compare?: ((l, r) => number) = (l, r) => l - r)：从可迭代集合 collection 创建一个最小堆（较小的先 pop 出来），使用 compare 比较大小（接受两个参数，首个参数较小则返回 true，否则返回 false，详见示例）。

.push(element: any)：把 element 加入堆中。

.pop()：从堆中弹出最小元素并返回，如果堆是空的则返回 undefined。

.top()：返回堆顶的元素（最小的元素），如果堆是空的则返回 undefined。

.size()：返回堆里的元素个数。

let heap = new Heap()
heap.push(2)
heap.push(3)
heap.push(1)
while (heap.size()) console.log(heap.pop()) // 输出 1, 2, 3

let maxHeap = new Heap((lhs, rhs) => rhs - lhs)
maxHeap.push(2)
maxHeap.push(3)
maxHeap.push(1)
// 等价于 maxHeap = new Heap([2, 3, 1], (lhs, rhs) => rhs - lhs)
while (maxHeap.size()) console.log(maxHeap.pop()) // 输出 3, 2, 1

new PriorityQueue(collection?: Iterable, compare?: ((l, r) => number) = (l, r) => l - r)：从可迭代集合 collection 创建一个最小堆（较小的先 pop 出来），使用 compare 比较大小（接受两个参数，首个参数较小则返回 true，否则返回 false，详见示例）。

.offer(element: any)：把 element 加入堆中。

.push(element: any)：同上。

.poll()：从队列中弹出最小元素并返回，如果堆是空的则返回 undefined。

.pop()：同上。

.peek()：返回队列顶的元素（最小的元素），如果堆是空的则返回 undefined。

.top()：同上。

.has(element: any)：返回布尔值，表示是否包含 element。

.size()：返回队列里的元素个数。

.remove(element: any)：从队列里删除 element。

let queue = new PriorityQueue()
queue.offer(3)
queue.offer(2)
queue.offer(1)
while (heap.size()) console.log(heap.poll()) // 输出 1, 2, 3

queue = new PriorityQueue((lhs, rhs) => rhs - lhs)
queue.offer(3)
queue.offer(2)
queue.offer(1)
// 等价于 queue = new PriorityQueue([3, 2, 1], (lhs, rhs) => rhs - lhs)
while (queue.size()) console.log(queue.poll()) // 输出 3, 2, 1

new RemovableHeap(collection?: Iterable, compare?: ((l, r) => number) = (l, r) => l - r)：从可迭代集合 collection 创建一个最小堆（较小的先 pop 出来），使用 compare 比较大小（接受两个参数，首个参数较小则返回 true，否则返回 false，详见示例）。

.push(element: any)：把 element 加入堆中。

.pop()：从堆中弹出最小元素并返回，如果堆是空的则返回 undefined。

.top()：返回堆顶的元素（最小的元素），如果堆是空的则返回 undefined。

.has(element: any)：返回布尔值，表示是否包含 element。

.size()：返回堆里的元素个数。

.remove(element: any)：从堆里删除 element。

let heap = new RemovableHeap()
heap.push(2)
heap.push(3)
heap.push(1)
heap.remove(2)
while (heap.size()) console.log(heap.pop()) // 输出 1, 3

new RemovableHeap(collection?: Iterable, compare?: ((l, r) => number) = (l, r) => l - r)：从可迭代集合 collection 创建一个最小堆（较小的先 pop 出来），使用 compare 比较大小（接受两个参数，首个参数较小则返回 true，否则返回 false，详见示例）。

.push(element: any)：把 element 加入堆中。

.popMin()：从堆中弹出最小元素并返回，如果堆是空的则返回 undefined。

.popMin()：从堆中弹出最大元素并返回，如果堆是空的则返回 undefined。

.top()：返回堆顶的元素（最小的元素），如果堆是空的则返回 undefined。

.has(element: any)：返回布尔值，表示是否包含 element。

.size()：返回堆里的元素个数。

.remove(element: any)：从堆里删除 element。

let heap = new RemovableDoubleHeap()
heap.push(2)
heap.push(3)
heap.push(1)
heap.popMin() // 1
heap.popMax() // 3

TypeScript JavaScript Test Cases

TreeSet

读写元素最坏情况时间复杂度为 log(n) 的有序集合，由红黑树实现。

new TreeSet(collection?: any[], compare?: ((l: any, r: any) => boolean) = ((l, r) => l - r))：创建一个集合，添加所有 collection 里的元素，并按照 compare 来比较元素大小（默认为升序）。

.add(val: any)：把元素 val 插入集合，如果 val 已存在则移除它。

.has(val: any)：如果 val 存在则返回 true，否则返回 false。

.delete(val: any)：从集合删除元素 val。

.floor(val: any)：找到并返回小于等于 val 的最大元素，如果不存在这样的元素则返回 undefined。

.ceil(val: any)：找到并返回大于等于 val 的最小元素，如果不存在这样的元素则返回 undefined。

.lower(val: any)：找到并返回小于 val 的最大元素，如果不存在这样的元素则返回 undefined。

.higher(val: any)：找到并返回大于 val 的最小元素，如果不存在这样的元素则返回 undefined。

.first()：返回集合中第一个元素，如果不存在这样的元素则返回 undefined。

.last()：返回集合中最后一个元素，如果不存在这样的元素则返回 undefined。

.shift()：删除集合中第一个元素并返回被删除元素的值，如果不存在这样的元素则返回 undefined。

.pop()：删除集合中最后一个元素并返回被删除元素的值，如果不存在这样的元素则返回 undefined。

.size(): number：返回集合的大小。

.values()：返回从第一个元素到最后一个元素的 ES6 迭代器。

.rvalues()：返回从最后一个元素到第一个元素的 ES6 迭代器。

const set = new TreeSet()
set.add(3)
set.add(5)
set.add(7)
// 等价于
// const set = new TreeSet([3, 5, 7], (l, r) => l - r);

set.ceil(4) // 5 is the smallest element >= 4
set.ceil(5) // 5 is the smallest element >= 5

TreeMultiSet

读写元素最坏情况时间复杂度为 log(n) 的有序集合，和 TreeSet 不同的是它允许多个等价的键存在，由红黑树实现。

new TreeSet(collection?: any[], compare?: ((l: any, r: any) => boolean) = ((l, r) => l - r))：创建一个集合，添加所有 collection 里的元素，并按照 compare 来比较元素大小（默认为升序）。

.add(val: any)：把元素 val 插入集合。

.has(val: any)：如果 val 存在则返回 true，否则返回 false。

.delete(val: any)：从集合删除元素 val。

.floor(val: any)：找到并返回小于等于 val 的最大元素，如果不存在这样的元素则返回 undefined。

.ceil(val: any)：找到并返回大于等于 val 的最小元素，如果不存在这样的元素则返回 undefined。

.lower(val: any)：找到并返回小于 val 的最大元素，如果不存在这样的元素则返回 undefined。

.higher(val: any)：找到并返回大于 val 的最小元素，如果不存在这样的元素则返回 undefined。

.fisrt()：返回集合中第一个元素，如果不存在这样的元素则返回 undefined。

.last()：返回集合中最后一个元素，如果不存在这样的元素则返回 undefined。

.shift()：删除集合中第一个元素并返回被删除元素的值，如果不存在这样的元素则返回 undefined。

.pop()：删除集合中最后一个元素并返回被删除元素的值，如果不存在这样的元素则返回 undefined。

.size(): number：返回集合的大小。

.values()：返回从第一个元素到最后一个元素的 ES6 迭代器。

.rvalues()：返回从最后一个元素到第一个元素的 ES6 迭代器。

TypeScript JavaScript Test Cases

一个动态大小的位集合。由 BigInt 实现，占用空间很小，但独写性能不如数组。

new BitSet(val:(string|number|bigint) = 0, N = Infinity)：创建一个 BitSet 对象，输入可以是数字，BigInt，也可以是由 "0" 和 "1" 构成的字符串，位长度为 N，默认容量为 Infinity。

.capacity()：返回集合的容量。

.count()：返回集合中 1 的位数。

.set(i: number, val: boolean | 1 | 0)：把下标为 i 的位设置位 val。

.get(i: number): 1 | 0：返回下表为 i 的位的值。

.toString()：返回一个由 "1" 和 "0" 构成的字符串，表示这个集合。

.shift(len: number)：返回一个新的 BitSet，它的值是 this 左移 len 位。

.unshift(len: number)：返回一个新的 BitSet，它的值是 this 右移 len 位。

.and(rhs: BitSet)：返回一个新的 BigSet，它的值是 this & rhs.

.or(rhs: BitSet)：返回一个新的 BigSet，它的值是 this | rhs.

.xor(rhs: BitSet)：返回一个新的 BigSet，它的值是 this ^ rhs.

.negate(rhs: BitSet)：返回一个新的 BigSet，它的值是 !this.

TypeScript JavaScript Test Cases

一个树状数组的实现，也叫 Fenwick Tree, Binary Indexed Tree，BIT。

new BIT(size: number)：创建一个大小为 size 的 BIT。

.update(index: number, value: number)：更新下标（从 1 开始）index 处的值为 value。

.increment(index: number, diff: number)：把下标（从 1 开始）index 处的值增加 diff。

let bit = new BIT(10)
bit.update(1, 10)
bit.update(2, 20)
bit.update(10, 100)
bit.sum(5) // elements in [1, 5] sums to 10 + 20 = 30
bit.sum(10) // elements in [1, 10] sums to 10 + 20 + 100 = 130

TypeScript JavaScript Test Cases

一个数组二叉树实现的线段树，聚合方式默认为前缀和。

new SegmentTree(N: number, aggregate = (a, b) => a + b, initial = 0)：创建一个大小为 N 的线段树，采用 aggregate 进行聚合，初始值为 initial。

.update(index: number, value: T)：更新下标（从 0 开始）index 处的值为 value。

.query(l: number, r: number): 求 [l, r] 范围的聚合，注意包含 l 和 r 处的元素。

.prefix(index: number): 相当于 .query(0, index)，求 [0, index] 范围内的前缀和，注意包含 index 元素。

.valueAt(index: number)：返回下标 index 处的元素。

.floor(val: any)：找到并返回聚合值小于等于 val 的最大元素下标，如果不存在这样的元素则返回 -1。

.ceil(val: any)：找到并返回聚合值大于等于 val 的最小元素下标，如果不存在这样的元素则返回 Infinity。

.lower(val: any)：找到并返回聚合值小于 val 的最大元素下标，如果不存在这样的元素则返回 -1。

.higher(val: any)：找到并返回聚合值大于 val 的最小元素下标，如果不存在这样的元素则返回 Infinity。

const sumTree = new SegmentTree(5)
sumTree.update(0, 1)
sumTree.update(1, 2)
sumTree.update(2, 3)
sumTree.update(3, 4)

sumTree.query(0, 2) // 6
sumTree.prefix(0) // 1
sumTree.prefix(1) // 3
sumTree.prefix(2) // 6
sumTree.prefix(3) // 10

sumTree.ceil(7) // 3
sumTree.ceil(6) // 2
sumTree.ceil(5) // 2
sumTree.ceil(11) // Infinity

const maxTree = new SegmentTree(5, Math.max)
maxTree.update(0, 1)
maxTree.prefix(0) // 1

maxTree.update(1, 3)
maxTree.prefix(1) // 3
maxTree.prefix(2) // 3

maxTree.update(2, 2)
maxTree.prefix(2) // 3

TypeScript JavaScript Test Cases

支持路径压缩和按秩合并的并查集实现，提供接近常数时间复杂度（Inverse Ackermann Function）的 find/union 操作。

new DSU(N: number)：创建一个大小为 N 的并查集。

.find(x: number)：找到值 x 对应的组，返回表示这个组的数字。

.union(x: number, y: number)：合并 x 和 y 所属的组并返回 true，如果 x 和 y 已经在同一组则返回 false。

TypeScript JavaScript Test Cases

prime(n: number)：返回第 n（从 1 开始）个质数，例如 prime(1) 返回 2。

primesLeq(n: number): 得到小于等于 n 的所有质数，返回一个数组。

isPrime(n)：如果 n 是质数则返回 true，否则返回 false。

primeFactors(n)：返回 n 的所有质数因子，键为质数，值为因子的指数。

let factors = primeFactors(24) // 24 = 2*2*2*3 = 2**3 + 3**1
for (let [prime, count] of factors) {
  console.log(prime, count)
}
// 输出
// 2 3
// 3 1

TypeScript JavaScript Test Cases

factorial(n: number)：返回 n 的阶乘，例如 factorial(3) 返回 6。

modularFactorial(n: number, MOD: number)：模阶乘，同 factorial()，区别是结果会对 MOD 取模。

factorialSequence(n: number)：得到阶乘序列，下标 i 的值表示 i 的阶乘。例如 factorialSequence(3) 返回 [1, 1, 2, 6]。

modularFactorialSequence(n: number, MOD: number)：得到取模的阶乘序列，同 factorialSequence()，区别是结果会对 MOD 取模。

pascalsTriangle(n: number)：返回第 n 个帕斯卡三角，例如 pascalsTriangle(3) 返回 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]。其中 P[n][k] 表示 C(n, k) 的值。

modularPascalsTriangle(n: number, MOD: number)：返回第 n 个帕斯卡三角，其中每个值对 MOD 取模。

binomialCoefficient(n: number, k: number)：返回二项式系数 C(n, k)，即从 n 个互不相同的元素中取 k 个元素的组合数。

moduleBinomialCoefficient(n: number, k: number, MOD: number)：返回二项式系数，它的值对 MOD 取模。

TypeScript JavaScript Test Cases

gcd(a: number, b: number)：运行欧几里得算法，得到最大公约数。

gcdExtended(a: number, b: number)：运行扩展欧几里得算法，得到 [gcd, x, y] 数组，其中第一个元素 gcd 为最大公约数，且 gcd === x * a + y * b。

modularInverse(a: number, n: number)：返回 a 的模逆元，即 a^-1 mod n。如果 a 和 n 不互质则抛出异常。

TypeScript JavaScript Test Cases

new RollingHash(L: number, M: number)：创建一个滚动哈希对象。L 是滚动窗口的长度；M 是倍增的进制，通常取大于被哈希数的最大值的一个质数。例如被哈希的是 0-26，该质数可以取 29 或 31。

.getValue()：得到当前的哈希值。

.digest(value: number)：加一个数到滚动哈希里。

.degest(value: number)：退出一个数到滚动哈希里。注意要在刚超过窗口长度时（长度为 L + 1）的时候退出。一般需要调用 .digest() 之后调用 .degest()。例如：

const LEN = 3,
  hash = new RollingHash(LEN, 29)
const str = 'abcdabc'
const arr = [...str].map((c) => c.charCodeAt() - 97)
for (let i = 0; i < arr.length; i++) {
  hash.digest(arr[i])
  if (i >= LEN) hash.degest(arr[i - LEN])
  console.log(hash.getKey())
}
// 输出，注意两次到 c 时哈希值相等
0, 1, 31, 902, 1769, 2524, 31

new BiRollingHash(L: number, M1: number, M2: number)：创建一个滚动哈希对象，其中封装两个 RollingHash。L 是滚动窗口的长度；M1 是第一个哈希的倍增进制，M2 是第二个哈希的倍增进制。

BiRollingHash 的其他接口与 RollingHash 一致，除了 .getKey() 返回的是一个字符串，逗号分隔两个哈希值。例如：

const LEN = 3,
  hash = new BiRollingHash(LEN, 29, 31)
const str = 'abcdabc'
const arr = [...str].map((c) => c.charCodeAt() - 97)
for (let i = 0; i < arr.length; i++) {
  hash.digest(arr[i])
  if (i >= LEN) hash.degest(arr[i - LEN])
  console.log(hash.getKey())
}
// 输出，注意两次到 c 时哈希值相等
'0,0', '1,1', '31,33', '902,1026', '1769,2015', '2524,2884', '31,33'

TypeScript JavaScript Test Cases

memorized(fn: Function, getKey? ((...args: any[]) => string) = ((...args) => args.join(',')))：返回一个新的函数，记录并缓存 fn 的调用参数和返回值。可以自定义 getKey 来避免键的冲突或降低键的空间占用。

create2DArray(N, M, val)：创建一个 N 行 M 列的二维数组，所有元素的值初始化为 val。

create3DArray(N, M, D, val)：创建一个 N 行 M 列，深度为 D 的二维数组，所有元素的值初始化为 val。

adjacent2D(arr, i, j)：迭代 [i, j] 周围四个方向的合法下标。

let arr = [
  [11, 12, 13],
  [21, 22, 23],
  [31, 32, 33]
]
for (let [ni, nj] of adjacent2D(arr, 1, 0)) {
  console.log([ni, nj]) // [0, 0], [1, 1], [2, 0]
}

valid2D(arr, i, j)：测试 [i, j] 对于二位数组 arr 是否合法，如果合法则返回 true 否则返回 false。

在 Node.js 里可以通过 npm 安装后使用 contest.js。

CommonJS:

const { Heap } = require('contest.js')
let heap = new Heap()

ES Module:

import { Heap } from 'contest.js'

const heap = new Heap()

欢迎任何形式的贡献，我都会给予帮助！你可以：

• 新增算法：某个门类中缺少的算法/数据结构，或者缺少的门类。
• 增强既有算法：更可读，更简单，或性能更好。
• 工程：改善测试覆盖率，补充和翻译文档，中/英/其他。
• 其他：发挥你的想象力！

• 如何设计接口？
  • 是否有类似的 ES6 类和方法？参考它们！比如 BitSet 里方法的命名可以参考 Set。
  • 是否有类似的 C++ 标准库、STL 或 Java 类？参考它们！比如 algorithm.ts 的内容参考 <algorithm> 库。
• 如何解决依赖？
  • 尽量减少依赖，这样单个文件拷贝出去可以直接使用。例如 swap 方法直接写在需要使用的文件里。
  • 如果有若干方法或类互相依赖，建议合并为一个文件，但单个文件不要太大。例如 TreeSet 和 RBTree 仍然是两个文件。
• 关于代码风格
  • npm run lint 可以通过就基本可以了！
  • export 请写文件尾部，拷贝上面的内容时不需要逐个删除 export。
  • 请添加对应的 test，确保覆盖率不下降。
  • 渐进复杂度相同的情况下，优先确保简单性和可读性，而非性能。
  • 只需要提供 TypeScript 版本，mjs 会在合入后自动生成。请通过 npm run build 确保生成的 lib/*.mjs 仍然可读，比如避免用私有方法语法，直接加前缀下划线可以避免 msj 中包含不可读的代码。