共计 9976 个字符，预计需要花费 25 分钟才能阅读完成。
简略总结一些用 JavaScript 刷力扣的根本调试技巧。最近又刷了点题，总结了些数据结构和算法，心愿能对各为 JSer 刷题提供帮忙。
此篇文章次要想给大家一些开箱即用的 JavaScipt 版本的代码模板，波及到较简单的知识点，原理局部可能会省略，有需要的话前面有工夫能够给局部知识点独自写一篇具体的解说。
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 被一些算法初学者认为是高难度数据结构，个别遇到间接放弃那种。所以我想了下几句话应该也解释不清，那就跳过原理间接上模板吧。:P
先简略说一下背景，KMP 解决的是子串查找的问题。给两个字符串 S 和T，求 T 是否是 S 的子串。解决办法是先预处理 T，求出T 的next数组，其中 next[i] 代表 T 的子串 T[0...i-1]（即T.substring(0, i)） 最长相等的前缀后缀 的长度。
嘛，最长相等的前缀后缀，就是说，比方字符串 "abcuuabc" 最长相等的前缀后缀就是abc，那么其长度就应该是3。
而后借助 next 数组，能够在线性工夫复杂度内求出 T 是否为 S 的子串，首次呈现下标，以及呈现次数。
模板代码：
// 求字符串 s 的 next 数组
function getNext(s) {
let len = s.length;
let next = new Array(len + 1);
let j = 0, k = -1;
next[0] = -1;
while (j < len) {if (k == -1 || s[j] === s[k]) next[++j] = ++k;
else k = next[k];
}
return next;
}
// 求字符串 t 在字符串 s 中第一次呈现的下标 不存在则返回 -1
function findIndex(s, t) {
let i = 0, j = 0;
let next = getNext(t);
let slen = s.length, tlen = t.length;
while (i < slen && j < tlen) {if (j === -1 || s[i] === t[j]) ++i, ++j;
else j = next[j];
}
return j === tlen ? i - tlen : -1;
}
// 求字符串 t 在字符串 s 呈现的次数
function findCount(s, t) {
let ans = 0;
let i = 0, j = 0;
let next = getNext(t);
let slen = s.length, tlen = t.length;
while (i < slen && j < tlen) {if (j === -1 || s[i] === t[j]) ++i, ++j;
else j = next[j];
if (j === tlen) {
++ans;
j = next[j];
}
}
return ans;
}
如果屡次计算子串雷同的话，next数组能够预处理，不须要每次在求 index 时再计算。
举个例子吧，LeetCode 1392. 最长高兴前缀
「高兴前缀」是在原字符串中既是 非空 前缀也是后缀（不包含原字符串本身）的字符串。
给你一个字符串 s，请你返回它的 最长高兴前缀。
如果不存在满足题意的前缀，则返回一个空字符串。
咱们会发现这不就是 next 数组么，所以我记得这次周赛会 KMP 的同学间接 copy 就得分了 …..
AC 代码；
// getNext 定义参考下面模板
/** * @param {string} s
* @return {string} */
var longestPrefix = function(s) {
let len = s.length;
let next = getNext(s);
let ansLen = next[len] == len ? len - 1 : next[len]; // 不蕴含原字符串 须要非凡判断下
return s.substring(0, ansLen);
};
再来一个 LeetCode 28. 实现 strStr() 求一个字符串在另一个字符串中首次呈现的地位，就是 indexOf 的实现，其实也就是模板中的 findIndex 函数。
AC 代码：
// findIndex 定义参考模板
/** * @param {string} haystack
* @param {string} needle
* @return {number} */
var strStr = function(haystack, needle) {return findIndex(haystack, needle);
};
优先队列（堆）
优先队列，咱们给每个元素定义优先级，每次取队列中的值都取的是优先级最大的数。
其余的语言中都自带优先队列的实现，JSer 就只能 QAQ……所以我本人写了一个优先队列，就是通过堆来实现。（原理就不讲啦，学过堆排序的应该懂~（趴
class PriorityQueue {/** * 构造函数 能够传入比拟函数自定义优先级 默认是最小值排在最前 * @param {function} compareFunc 比拟函数 compareFunc(a, b) 为 true 示意 a 的优先级 > b */
constructor(compareFunc) {this.queue = [];
this.func = compareFunc || ((a, b) => a < b);
}
/** * 向优先队列增加一个元素 */
push(ele) {this.queue.push(ele);
this.pushup(this.size() - 1)
}
/** * 弹出最小值并返回 */
pop() {let { queue} = this;
if (queue.length <= 1) return queue.pop();
let min = queue[0];
queue[0] = queue.pop();
this.pushdown(0);
return min;
}
/** * 返回最小值 */
top() {return this.size() ? this.queue[0] : null;
}
/** * 返回队列中元素的个数 */
size() {return this.queue.length;}
/** * 初始化堆 */
setQueue(queue) {
this.queue = queue;
for (let i = (this.size() >> 1); i >= 0; i--) {this.pushdown(i);
}
}
/** * 调整以保障 queue[index] 是子树中最小的 * */
pushdown(index) {let { queue, func} = this;
let fa = index;
let cd = index * 2 + 1;
let size = queue.length;
while (cd < size) {if (cd + 1 < size && func(queue[cd + 1], queue[cd])) cd++;
if (func(queue[fa], queue[cd])) break;
// 替换 queue[fa] 和 queue[cd]
[queue[fa], queue[cd]] = [queue[cd], queue[fa]];
// 持续解决子树
fa = cd;
cd = fa * 2 + 1;
}
}
/** * 调整 index 到非法地位 */
pushup(index) {let { queue, func} = this;
while (index) {const fa = (index - 1) >> 1;
if (func(queue[fa], queue[index])) {break;}
[queue[fa], queue[index]] = [queue[index], queue[fa]];
index = fa;
}
}
}
举个例子，LeetCode 23. 合并 K 个升序链表 一道艰难题目哦~
给你一个链表数组，每个链表都曾经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
做法很简略，把链表都放到优先队列里，每次取值最小的链表就行。具体实现看代码。
/** * @param {ListNode[]} lists
* @return {ListNode} */
var mergeKLists = function(lists) {let queue = new PriorityQueue((a, b) => a.val < b.val);
lists.forEach(list => {list && queue.push(list);
});
const dummy = new ListNode(0);
let cur = dummy;
while (queue.size()) {let node = queue.pop();
if (node.next) queue.push(node.next);
cur.next = new ListNode(node.val);
cur = cur.next;
}
return dummy.next;
};
Trie（字典树 / 前缀树）
字典树应该算是一个比较简单而且直观的数据结构~ 字典树模板题能够看 LeetCode 208. 实现 Trie (前缀树)
/** * Initialize your data structure here. */
var Trie = function() {this.nodes = [];
};
/** * Inserts a word into the trie. * @param {string} word
* @return {void} */
Trie.prototype.insert = function(word) {
let nodes = this.nodes;
for (let w of word) {if (!nodes[w]) {nodes[w] = {};}
nodes = nodes[w];
}
nodes.end = true;
};
/** * Returns if the word is in the trie. * @param {string} word
* @return {boolean} */
Trie.prototype.search = function(word) {
let nodes = this.nodes;
for (let w of word) {if (!nodes[w]) {return false;}
nodes = nodes[w];
}
return !!nodes.end;
};
/** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix
* @return {boolean} */
Trie.prototype.startsWith = function(prefix) {
let nodes = this.nodes;
for (let w of prefix) {if (!nodes[w]) {return false;}
nodes = nodes[w];
}
return true;
};
字典树的变种利用，LeetCode 421. 数组中两个数的最大异或值 参考：题解
咱们也能够将数组中的元素看成长度为 31 的字符串，字符串中只蕴含 0 和 1。如果咱们将字符串放入字典树中，那么在字典树中查问一个字符串的过程，恰好就是从高位开始确定每一个二进制位的过程。对于一个数求异或和的最大值，就是从最高位开始，每一位都找异或和最大的那个分支。
var Trie = function() {this.nodes = [];
};
Trie.prototype.insert = function(digit) {
let nodes = this.nodes;
for (let d of digit) {if (!nodes[d]) {nodes[d] = [];}
nodes = nodes[d];
}
};
Trie.prototype.maxXor = function(digit) {
let xor = 0;
let nodes = this.nodes;
for (let i = 0; i < digit.length; i++) {let d = digit[i];
if (nodes[d ^ 1]) {xor += 1 << (digit.length - i - 1);
nodes = nodes[d ^ 1];
} else {nodes = nodes[d];
}
}
return xor;
};
/** * @param {number[]} nums
* @return {number} */
var findMaximumXOR = function(nums) {let trie = new Trie();
let maxXor = 0;
for (let x of nums) {let binaryX = x.toString(2);
// 因为 0 <= nums[i] <= 2^31 - 1 所以最多为 31 位
// 补前缀 0 对立变成 31 位
binaryX = ('0'.repeat(31) + binaryX).substr(-31);
// 插入 Trie
trie.insert(binaryX);
maxXor = Math.max(maxXor, trie.maxXor(binaryX));
}
return maxXor;
};
总结
临时就想到这么多比拟常见的数据结构。如果有其余的能够在评论区补充，如果我会的话会后续加上的。
JSer 冲鸭！！！
