Repository files navigation

English

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

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

有用链接：

• 在线预览：https://harttle.land/contest.js
• 在 LeetCode 页面执行/判定用例：https://greasyfork.org/zh-CN/scripts/402276-leetcode-helper-for-javascript

索引

TypeScriptJavaScriptTest Cases

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

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

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

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

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

letarr=[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 方法。

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

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

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

TypeScriptJavaScriptTest 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

TypeScriptJavaScriptTest Cases

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

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

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

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

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

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

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

TypeScriptJavaScriptTest Cases

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

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

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

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

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

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

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

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

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

letdeque=newDeque([1,2,3])deque.push(4)deque.unshift(0)deque.pop()// returns 4deque.pop()// returns 3deque.shift()// returns 0for(letvalofdeque){console.log(val)// outputs 1 and 2}

TypeScriptJavaScriptTest 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()：返回堆里的元素个数。

letheap=newHeap()heap.push(2)heap.push(3)heap.push(1)while(heap.size())console.log(heap.pop())// 输出 1, 2, 3letmaxHeap=newHeap((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。

letqueue=newPriorityQueue()queue.offer(3)queue.offer(2)queue.offer(1)while(heap.size())console.log(heap.poll())// 输出 1, 2, 3queue=newPriorityQueue((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。

letheap=newRemovableHeap()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。

letheap=newRemovableDoubleHeap()heap.push(2)heap.push(3)heap.push(1)heap.popMin()// 1heap.popMax()// 3

TypeScriptJavaScriptTest 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 迭代器。

constset=newTreeSet()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 >= 4set.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 迭代器。

TypeScriptJavaScriptTest Cases

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

new TreeMap<K, V>(collection?: [K, V][], compare?: ((lhs: K, rhs: K) => boolean) = ((l, r) => l - r))：创建一个映射，添加所有collection 里的元素，并按照compare 来比较元素大小（默认为升序）。

.set(key: K, value: V)：把键值对key,value 插入映射，如果key 已存在则移除它。

.has(key: K): boolean：如果key 存在则返回true，否则返回false。

.delete(key: K)：从映射删除元素key。

.floor(key: K): [K, V]：找到并返回小于等于key 的最大键值对，如果不存在这样的元素则返回undefined。

.ceil(key: K): [K, V]：找到并返回大于等于key 的最小键值对，如果不存在这样的元素则返回undefined。

.lower(key: K): [K, V]：找到并返回小于key 的最大键值对，如果不存在这样的元素则返回undefined。

.higher(key: K): [K, V]：找到并返回大于key 的最小键值对，如果不存在这样的元素则返回undefined。

.first(): [K, V]：返回映射中第一个键值对，如果不存在这样的元素则返回undefined。

.last(): [K, V]：返回映射中最后一个键值对，如果不存在这样的元素则返回undefined。

.shift(): [K, V]：删除映射中第一个键值对并返回被删除元素的值，如果不存在这样的元素则返回undefined。

.pop(): [K, V]：删除映射中最后一个键值对并返回被删除元素的值，如果不存在这样的元素则返回undefined。

.size(): number：返回映射的大小。

.keys()：返回从第一个键到最后一个键的 ES6 迭代器。

.rkeys()：返回从最后一个键到第一个键的 ES6 迭代器。

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

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

constmap=newTreeMap()map.set(3,'c')map.set(5,'e')map.set(7,'g')// 等价于// const map = new TreeMap([[3, 'c'], [5, 'e'], [7, 'g']], (l, r) => l - r);map.ceil(4)// [5, 'e] is the smallest element >= 4map.ceil(5)// [5, 'e'] is the smallest element >= 5

TypeScriptJavaScriptTest 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.

TypeScriptJavaScriptTest 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。

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

TypeScriptJavaScriptTest 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 的最小元素下标，如果不存在这样的元素则返回-1。

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

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

constsumTree=newSegmentTree(5)sumTree.update(0,1)sumTree.update(1,2)sumTree.update(2,3)sumTree.update(3,4)sumTree.query(0,2)// 6sumTree.prefix(0)// 1sumTree.prefix(1)// 3sumTree.prefix(2)// 6sumTree.prefix(3)// 10sumTree.ceil(7)// 3sumTree.ceil(6)// 2sumTree.ceil(5)// 2sumTree.ceil(11)// -1constmaxTree=newSegmentTree(5,Math.max)maxTree.update(0,1)maxTree.prefix(0)// 1maxTree.update(1,3)maxTree.prefix(1)// 3maxTree.prefix(2)// 3maxTree.update(2,2)maxTree.prefix(2)// 3

TypeScriptJavaScriptTest Cases

提供DirectedGraph 和UndirectedGraph，用Map 实现，支持稀疏图。

new DirectedGraph(N: number)：创建一个有N 个节点的有向图。

.addEdge(u, v, dist?)：添加一条从u 到v 的边，距离为dist。

.removeEdge(u, v)：移除一条边。

.removeNode(u)：移除一个节点，会同时移除它的所有边。

.size(): number：返回图的节点数目。

.getLeaves(): IterableIterator：返回叶节点的数目（入度小于等于1），迭代期间移除边导致的新叶节点会加入迭代。

.getDistance(u, v): number：返回u 和v 节点的距离，如果没有直接连接起来则返回Infinity。

.getChildren(u): IterableIterator：返回迭代器，包括u 的所有子节点。

.getParents(u): IterableIterator：返回迭代器，包括u 的所有父节点。

.getAllEdges(): IterableIterator<[TNode, TNode, number]>: 返回迭代器，包括图中的所有边。

new UndirectedGraph(N: number)：创建一个有N 个节点的无向图。

.addEdge(u, v, dist?)：同DirectedGraph。

.removeEdge(u, v)：同DirectedGraph。

.removeNode(u)：同DirectedGraph。

.size(): number：同DirectedGraph。

.getLeaves(): IterableIterator：同DirectedGraph。

.getDistance(u, v): number：同DirectedGraph。

.getAdjacent(u): IterableIterator：同DirectedGraph#getChildren()。

.getAllEdges(): IterableIterator<[TNode, TNode, number]>: 同DirectedGraph。

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

constG=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 的最短路径长度。

constG=newMap()G.set(0,newMap([[1,10]]))G.set(1,newMap([[0,30],[2,50]]))dijkstra(0,G)// Map(3) { 0 => 0, 1 => 10, 2 => 60 }

constG=newcreateGraph([[0,1,10],[1,0,30],[1,2,50],])dijkstra(0,G)// Map(3) { 0 => 0, 1 => 10, 2 => 60 }

TypeScriptJavaScriptTest 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。

TypeScriptJavaScriptTest Cases

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

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

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

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

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

TypeScriptJavaScriptTest Cases

fact：长度为 N 的排列数，例如fact[0] = fact[1] = 1，fact[2] = 2。

factInvs：长度为 N 的排列数的模逆元。

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

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

arrangement(n: number, k: number)：返回 A(n, k)，即从 n 个互不相同的元素中取 k 个元素的排列数。

TypeScriptJavaScriptTest Cases

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

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

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

TypeScriptJavaScriptTest Cases

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

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

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

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

constLEN=3,hash=newRollingHash(LEN,29)conststr='abcdabc'constarr=[...str].map((c)=>c.charCodeAt()-97)for(leti=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() 返回的是一个字符串，逗号分隔两个哈希值。例如：

constLEN=3,hash=newBiRollingHash(LEN,29,31)conststr='abcdabc'constarr=[...str].map((c)=>c.charCodeAt()-97)for(leti=0;i<arr.length;i++){hash.digest(arr[i])if(i>=LEN)hash.degest(arr[i-LEN])console.log(hash.getKey())}// 输出，注意两次到 c 时哈希值相等// 0// 1000000008// 33000000262// 1026000008084// 2015000015874// 2884000022712// 33000000262

TypeScriptJavaScriptTest Cases

new StringHash(M: number)：创建一个字符串哈希对象。M 是倍增的进制，通常取大于被哈希数的最大值的一个质数。例如被哈希的是 0-26，该质数可以取 29 或 31。

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

.digest(value: number)：加一个数到字符串哈希里。

consthash=newStringHash(LEN,29)conststr='abcdabc'constarr=[...str].map((c)=>c.charCodeAt()-97)for(leti=0;i<arr.length;i++){hash.digest(arr[i])console.log(hash.getKey())}

new BiStringHash(M1: number, M2: number)：创建一个字符串哈希对象，其中封装两个 StringHash。M1 是第一个哈希的倍增进制，M2 是第二个哈希的倍增进制。

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

consthash=newBiStringHash(29,31)conststr='abcdabc'constarr=[...str].map((c)=>c.charCodeAt()-97)for(leti=0;i<arr.length;i++){hash.digest(arr[i])console.log(hash.getKey())}

TypeScriptJavaScriptTest Cases

createTree(N: number, edges: [number, number][]): TreeNode[]: 从边的数组[number, number] 生成一棵树，返回节点列表，其中第一个节点为树的根节点。

constnodes=createTree(3,[[0,1],[0,2]])console.log(nodes[0])// { index: 0, children: Map{[{index: 1, ...}, 1], [{index: 2, ...}, 1]}, depth: 0}console.log(nodes[1])// { index: 1, children: Map{}, parent: {index: 0, ...}, depth: 1}console.log(nodes[2])// { index: 2, children: Map{}, parent: {index: 0, ...}, depth: 1}

createWeightedTree(N: number, edges: [number, number, number][]): TreeNode[]: 从边的数组[number, number, number] 生成一棵有权重的树，返回节点列表，其中第一个节点为树的根节点。前两个数字为边的两个节点，最后一个数字为权重：

constnodes=createTree(3,[[0,1,10],[0,2,20]])console.log(nodes[0])// { index: 0, children: Map{[{index: 1, ...}, 10], [{index: 2, ...}, 20]}, depth: 0}console.log(nodes[1])// { index: 1, children: Map{}, parent: {index: 0, ...}, depth: 1}console.log(nodes[2])// { index: 2, children: Map{}, parent: {index: 0, ...}, depth: 1}

• new LCA(nodes: TreeNode[]): 创建一个根为nodes[0] 的 LCA 结构。
• .getLCA(u: number, v: number): 拿到u 和v 的最低公共祖先。

constnodes=createTree(6,[[0,1],[0,2],[1,4],[1,3],[4,5]])constlca=newLCA(nodes)console.log(lca.getLCA(3,5))// 1

TypeScriptJavaScriptTest 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] 周围四个方向的合法下标。

letarr=[[11,12,13],[21,22,23],[31,32,33]]for(let[ni,nj]ofadjacent2D(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')letheap=newHeap()

ES Module:

import{Heap}from'contest.js'constheap=newHeap()

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

• 代码：
  • 新增算法：某个门类中缺少的算法/数据结构，或者缺少的门类。
  • 增强既有算法：更可读，更简单，或性能更好。
• 测试：补充测试 case，改善测试覆盖率。
• 文档：文档中有不少描述不清或缺失的地方，比如漏了某个public 方法的描述、英文和中文不同步、标点空格使用错误或不一致、例子可以再丰富或方便理解一些。

• 如何设计接口？
  • 是否有类似的 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 中包含不可读的代码。