之前写了篇文章 用JavaScript刷LeetCode的正确姿势，简单总结一些用 JavaScript 刷力扣的基本调试技巧。最近又刷了点题，总结了些数据结构和算法，希望能对各为 JSer 刷题提供帮助。
此篇文章主要想给大家一些开箱即用的 JavaScipt 版本的代码模板，涉及到较复杂的知识点，原理部分可能会省略，有需要的话后面有时间可以给部分知识点单独写一篇详细的讲解。
走过路过发现 bug 请指出，拯救一个辣鸡（但很帅）的少年就靠您啦！！！
BigInt
众所周知，JavaScript 只能精确表达 Number.MIN_SAFE_INTEGER(-2^53+1) ~ Number.MAX_SAFE_INTEGER(2^53-1) 的值。
而在一些题目中，常常会有较大的数字计算，这时就会产生误差。举个栗子：在控制台输入下面的两个表达式会得到相同的结果：
>> 123456789*123456789 // 15241578750190520
>> 123456789*123456789+1 // 15241578750190520
而如果使用 BigInt 则可以精确求值：
>> BigInt(123456789)*BigInt(123456789) // 15241578750190521n
>> BigInt(123456789)*BigInt(123456789)+BigInt(1) // 15241578750190522n
可以通过在一个整数字面量后面加 n 的方式定义一个 BigInt ，如：10n，或者调用函数 BigInt()。上面的表达式也可以写成：
>> 123456789n*123456789n // 15241578750190521n
>> 123456789n*123456789n+1n // 15241578750190522n
BigInt 只能与 BigInt 做运算，如果和 Number 进行计算需要先通过 BigInt() 做类型转换。
BigInt 支持运算符，+、*、-、**、% 。除 >>>（无符号右移）之外的位操作也可以支持。因为 BigInt 都是有符号的， >>>（无符号右移）不能用于 BigInt。BigInt 不支持单目 (+) 运算符。
BigInt 也支持 / 运算符，但是会被向上取整。
const rounded = 5n / 2n; // 2n, not 2.5n
取模运算
在数据较大时，一般没有办法直接去进行计算，通常都会给一个大质数（例如，1000000007），求对质数取模后的结果。
取模运算的常用性质：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p) ^ b) % p
可以看出，加/减/乘/乘方，都可直接在运算的时候取模，至于除法则会复杂一些，稍后再讲。
举一个例子，LeetCode 1175. 质数排列
请你帮忙给从
1到n的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从1开始）上；你需要返回可能的方案总数。让我们一起来回顾一下「质数」：质数一定是大于
1的，并且不能用两个小于它的正整数的乘积来表示。由于答案可能会很大，所以请你返回答案 模 mod
10^9 + 7之后的结果即可。
题目很简单，先求出质数的个数 x，则答案为 x!(n-x)!（不理解的可以去看题解区找题解，这里就不详细解释了）
由于阶乘的值很大，所以在求阶乘的时候需要在运算时取模，同时这里用到了上面所说的BigInt。
/**
* @param {number} n
* @return {number}
*/
var numPrimeArrangements = function(n) {
const mod = 1000000007n;
// 先把100以内的质数打表（不想再写判断质数的代码了
const prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
// 预处理阶乘
const fac = new Array(n + 1);
fac[0] = 1n; // 要用bigint
for (let i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * BigInt(i) % mod;
}
// 先求n以内的质数的个数
const x = prime.filter(i => i <= n).length;
// x!(n-x)!
return fac[x] * fac[n - x] % mod;
};
快速幂
快速幂，顾名思义，快速求幂运算。原理也很简单，比如我们求 x^10 我们可以求 (x^5)^2 可以减少一半的运算。
假设我们求 (x^n)
- 如果
n是偶数，变为求(x^(n/2))^2 - 如果
n是奇数，则求(x^⌊n/2⌋)^2 * x（⌊⌋是向下取整）
因为快速幂涉及到的题目一般数据都很大，需要取模，所以加了取模运算。其中，代码中 n>>=1 相当于 n=n/2，if(n&1)是在判断n是否为奇数。
代码如下：
// x ^ n % mod
function pow(x, n, mod) {
let ans = 1;
while (n > 0) {
if (n & 1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}
return ans;
}
乘法逆元（数论倒数）
上面说了除法的取模会复杂一些，其实就是涉及了乘法逆元。
当我们求 (a/b)%p 你以为会是简单的 ((a%p)/(b%p))%p？当然不是！（反例自己想去Orz
假设有 (a*x)%p=1 则称 a和x关于p互为逆元（a 是 x 关于 p 的逆元，x 是 a 关于 p 的逆元）。比如：2*3%5=1 则 2 和 3 关于 5 互为逆元。
我们把 a 的逆元用 inv(a) 表示。那么：
(a/b) % p
= ( (a/b) * (b*inv(b)) ) % p // 因为(b*inv(b))为1
= (a * inv(b)) % p
= (a%p * inv(b)%p) % p
现在通过逆元神奇的把除法运算变没了~~~
问题在于怎么求乘法逆元。有两种方式，费马小定理 和 扩展欧几里德算法
不求甚解的我只记了一种解法，即费马小定理：a^(p-1) ≡ 1 (mod p)
由费马小定理我们可以推论：a^(p-2) ≡ inv(a) (mod p)
数学家的事我们程序员就不要想那么多啦，记结论就好了。即：
a关于p的逆元为a^(p-2)
好了，现在可以通过快速幂求出 a 的逆元了。
function inv(a, p) {
return pow(a, p - 2, p); // pow是上面定义的快速幂函数
}
（P.S.其实我数论很烂= =，平时都是直接记结论，所以此处讲解可能存在不准确的情况。仅供参考。
二分答案
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了“二分答案”。二分答案的时间复杂度是O(logN * (单次验证当前值是否满足条件的复杂度))
很多同学在边界问题上经常出bug，也会不小心写个死循环什么的，我总结了一个简单清晰不会出错的二分模板：
// isValid 判断某个值是否合法 根据题目要求实现
// 假设 如果x合法则大于x一定合法 如果x不合法则小于x一定不合法
// 求最小合法值
function binaryCalc() {
let l = 0, r = 10000; // 答案可能出现的最小值l和最大值r 根据题目设置具体值
let ans; // 最终答案
while (l <= r) {
let mid = (l + r) >> 1; // 位运算取中间值 相当于 floor((l+r)/2)
if (isValid(mid)) {
// 如果 mid 合法 则 [mid, r] 都是合法的
// 我们先把ans设置为当前获取的合法值的最小值 mid
ans = mid;
// 然后再去继续去求[l,mid-1]里面是否有合法值
r = mid - 1;
} else {
// 如果mid不合法 则[l,mid]都是不合法的
// 我们去[mid+1,r]中找答案
l = mid + 1;
}
}
return ans;
}
举一个简单的例子，LeetCode 69. x 的平方根 是一个二分模板题。题目要求是，给一个数字 x 求平方小于等于 x的最大整数。此处求的是最大值，和模板中对l和r的处理刚好相反。
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let l = 0, r = x; // 根据题目要求 答案可能的值最小为0 最大为x
let ans = 0; // 最终答案
function isValid(v) { // 判断一个数是否合法
return v * v <= x;
}
while (l <= r) {
let mid = (l + r) >> 1; // 取中间值
if (isValid(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
};
并查集
个人觉得并查集是非常精妙且简洁优雅的数据结构，推荐学习。
并查集应用场景为，存在一些元素，分别包含在不同集合中，需要快速合并两个集合，同时可快速求出两个元素是否处于同一集合。
简单的理解并查集的实现，就是把每一个集合都当做一棵树，每个节点都有一个父节点，每棵树都有一个根节点（根节点的父节点为其本身）。
判断是否同一集合：我们可以顺着节点的父节点找到该节点所在集合的根节点。当我们确定两个集合拥有同一个根节点，则证明两个节点处于同一个集合。
合并操作：分别取得两个节点所在集合的根节点，把其中一个根节点的父节点设置为另一个根节点即可。
可能说的比较抽象，想详细了解的同学可以自己深入学习，这里直接给出代码模板。
class UnionFind {
constructor(n) {
this.n = n; // 节点个数
// 记录每个节点的父节点 初始时每个节点自己为一个集合 即每个节点的父节点都是其本身
this.father = new Array(n).fill().map((v, index) => index);
}
// 寻找一个节点的根节点
find(x) {
// 如果父节点为其本身 则证明是根节点
if (x == this.father[x]) {
return x;
}
// 递归查询
// 此处进行了路径压缩 即将x的父节点直接设置为根节点 下一次查询的时候 将减少递归次数
return this.father[x] = this.find(this.father[x]);
}
// 合并x和y所在的两个集合
merge(x, y) {
const xRoot = this.find(x); // 找到x的根节点
const yRoot = this.find(y); // 找到y的根节点
this.father[xRoot] = yRoot; // 将xRoot的父节点设置为yRoot 即可将两个集合合并
}
// 计算集合个数
count() {
// 其实就是查询根节点的个数
let cnt = 0;
for (let i = 0; i < this.n; i++) {
if (this.father[i] === i) { // 判断是否为根节点
cnt++;
}
}
return cnt;
}
}
找一个并查集的题目，方便大家理解并查集的妙处。并查集的题目可以出得非常灵活，可能不会轻易看出是并查集。 LeetCode 947. 移除最多的同行或同列石头
n块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为
n的数组stones，其中stones[i] = [xi, yi]表示第i块石头的位置，返回 可以移除的石子 的最大数量。
此处参考了官方的题解
把二维坐标平面上的石头想象成图的顶点，如果两个石头横坐标相同、或者纵坐标相同，在它们之间形成一条边。
根据可以移除石头的规则：如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。可以发现：一定可以把一个连通图里的所有顶点根据这个规则删到只剩下一个顶点。
我们遍历所有的石头，发现如果有两个石头的横坐标或者纵坐标相等，则证明这两块石头应该在同一个集合（即上面说的连通图）里。那么最后每个集合只留一块石头，剩下的则全部可以被移除。
AC代码：
// 定义 UnionFind 相关代码
/**
* @param {number[][]} stones
* @return {number}
*/
var removeStones = function(stones) {
let n = stones.length;
let uf = new UnionFind(n);
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// 有两个石头的横坐标或者纵坐标相等 则合并
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
uf.merge(i, j);
}
}
}
// 石头总数减去集合的个数就是答案
return n - uf.count();
};
KMP
KMP 被一些算法初学者认为是高难度数据结构，一般遇到直接放弃那种。所以我想了下几句话应该也解释不清，那就跳过原理直接上模板吧。