尽管很多人都感觉前端算法弱，但其实 JavaScript 也能够刷题啊！最近两个月断断续续刷完了 leetcode 前 200 的 middle + hard，总结了一些刷题罕用的模板代码。
罕用函数
包含打印函数和一些数学函数。
const _max = Math.max.bind(Math);
const _min = Math.min.bind(Math);
const _pow = Math.pow.bind(Math);
const _floor = Math.floor.bind(Math);
const _round = Math.round.bind(Math);
const _ceil = Math.ceil.bind(Math);
const log = console.log.bind(console);
//const log = _ => {}
log 在提交的代码中当然是用不到的，不过在调试时非常有用。然而当代码外面加了很多 log 的时候，提交时还须要一个个正文掉就相当麻烦了，只有将 log 赋值为空函数就能够了。
举一个简略的例子，上面的代码是能够间接提交的。
// 计算 1+2+...+n
// const log = console.log.bind(console);
const log = _ => {}
function sumOneToN(n) {
let sum = 0;
for (let i = 1; i <= n; i++) {
sum += i;
log(`i=${i}: sum=${sum}`);
}
return sum;
}
sumOneToN(10);
位运算的一些小技巧
判断一个整数 x 的奇偶性：x & 1 = 1 (奇数)，x & 1 = 0 (偶数)
求一个浮点数 x 的整数局部：~~x，对于负数相当于 floor(x) 对于正数相当于 ceil(-x)
计算 2 ^ n：1 << n 相当于 pow(2, n)
计算一个数 x 除以 2 的 n 倍：x >> n 相当于 ~~(x / pow(2, n))
判断一个数 x 是 2 的整数幂（即 x = 2 ^ n）: x & (x - 1) = 0
※留神※：下面的位运算只对 32 位带符号的整数无效，如果应用的话，肯定要留神数！据！范！围！
记住这些技巧的作用：
晋升运行速度 ❌
晋升逼格 ✅
举一个实用的例子，疾速幂（原理自行 google）
// 计算 x^n n 为整数
function qPow(x, n) {
let result = 1;
while (n) {if (n & 1) result *= x; // 同 if(n%2)
x = x * x;
n >>= 1; // 同 n=floor(n/2)
}
return result;
}
链表
刚开始做 LeetCode 的题就遇到了很多链表的题。恶心心。最麻烦的不是写题，是调试啊！！于是总结了一些链表的辅助函数。
/** * 链表节点 * @param {*} val
* @param {ListNode} next
*/
function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
/** * 将一个数组转为链表 * @param {array} a
* @return {ListNode} */
const getListFromArray = (a) => {let dummy = new ListNode()
let pre = dummy;
a.forEach(x => pre = pre.next = new ListNode(x));
return dummy.next;
}
/** * 将一个链表转为数组 * @param {ListNode} node
* @return {array} */
const getArrayFromList = (node) => {let a = [];
while (node) {a.push(node.val);
node = node.next;
}
return a;
}
/** * 打印一个链表 * @param {ListNode} node */
const logList = (node) => {
let str = 'list:';
while (node) {
str += node.val + '->';
node = node.next;
}
str += 'end';
log(str);
}
还有一个罕用小技巧，每次写链表的操作，都要留神判断表头，如果创立一个空表头来进行操作会不便很多。
let dummy = new ListNode();
// 返回
return dummy.next;
应用起来超爽哒~ 举个例子。@leetcode 82。题意就是删除链表中间断雷同值的节点。
/** * @param {ListNode} head
* @return {ListNode} */
var deleteDuplicates = function(head) {
// 空指针或者只有一个节点不须要解决
if (head === null || head.next === null) return head;
let dummy = new ListNode();
let oldLinkCurrent = head;
let newLinkCurrent = dummy;
while (oldLinkCurrent) {
let next = oldLinkCurrent.next;
// 如果以后节点和下一个节点的值雷同 就要始终向前直到呈现不同的值
if (next && oldLinkCurrent.val === next.val) {while (next && oldLinkCurrent.val === next.val) {next = next.next;}
oldLinkCurrent = next;
} else {
newLinkCurrent = newLinkCurrent.next = oldLinkCurrent;
oldLinkCurrent = oldLinkCurrent.next;
}
}
newLinkCurrent.next = null; // 记得结尾置空~
logList(dummy.next);
return dummy.next;
};
deleteDuplicates(getListFromArray([1,2,3,3,4,4,5]));
deleteDuplicates(getListFromArray([1,1,2,2,3,3,4,4,5]));
deleteDuplicates(getListFromArray([1,1]));
deleteDuplicates(getListFromArray([1,2,2,3,3]));
本地运行后果
list: 1->2->5->end
list: 5->end
list: end
list: 1->end
是不是很不便！
矩阵（二维数组）
矩阵的题目也有很多，根本每一个须要用到二维数组的题，都波及到初始化，求行数列数，遍历的代码。于是简略提取进去几个函数。
/**
* 初始化一个二维数组
* @param {number} r 行数
* @param {number} c 列数
* @param {*} init 初始值
*/
const initMatrix = (r, c, init = 0) => new Array(r).fill().map(_ => new Array(c).fill(init));
/**
* 获取一个二维数组的行数和列数
* @param {any[][]} matrix
* @return [row, col]
*/
const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length];
/**
* 遍历一个二维数组
* @param {any[][]} matrix
* @param {Function} func
*/
const matrixFor = (matrix, func) => {matrix.forEach((row, i) => {row.forEach((item, j) => {func(item, i, j, row, matrix);
});
})
}
/**
* 获取矩阵第 index 个元素 从 0 开始
* @param {any[][]} matrix
* @param {number} index
*/
function getMatrix(matrix, index) {let col = matrix[0].length;
let i = ~~(index / col);
let j = index - i * col;
return matrix[i][j];
}
/**
* 设置矩阵第 index 个元素 从 0 开始
* @param {any[][]} matrix
* @param {number} index
*/
function setMatrix(matrix, index, value) {let col = matrix[0].length;
let i = ~~(index / col);
let j = index - i * col;
return matrix[i][j] = value;
}
找一个简略的矩阵的题示范一下用法。@leetcode 566。题意就是将一个矩阵重新排列为 r 行 c 列。
/** * @param {number[][]} nums
* @param {number} r
* @param {number} c
* @return {number[][]} */
var matrixReshape = function(nums, r, c) {
// 将一个矩阵重新排列为 r 行 c 列
// 首先获取原来的行数和列数
let [r1, c1] = getMatrixRowAndCol(nums);
log(r1, c1);
// 不非法的话就返回原矩阵
if (!r1 || r1 * c1 !== r * c) return nums;
// 初始化新矩阵
let matrix = initMatrix(r, c);
// 遍历原矩阵生成新矩阵
matrixFor(nums, (val, i, j) => {
let index = i * c1 + j; // 计算是第几个元素
log(index);
setMatrix(matrix, index, val); // 在新矩阵的对应地位赋值
});
return matrix;
};
let x = matrixReshape([[1],[2],[3],[4]], 2, 2);
log(x)
二叉树
当我做到二叉树相干的题目，我发现，我错怪链表了，呜呜呜这个更恶心。
当然对于二叉树，只有你把握先序遍历，后序遍历，中序遍历，层序遍历，递归以及非递归版，先序中序求二叉树，先序后序求二叉树，根本就能 AC 大部分二叉树的题目了（我瞎说的）。
二叉树的题目 input 个别都是层序遍历的数组，所以写了层序遍历数组和二叉树的转换，不便调试。
function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
/**
* 通过一个档次遍历的数组生成一棵二叉树
* @param {any[]} array
* @return {TreeNode}
*/
function getTreeFromLayerOrderArray(array) {
let n = array.length;
if (!n) return null;
let index = 0;
let root = new TreeNode(array[index++]);
let queue = [root];
while(index < n) {let top = queue.shift();
let v = array[index++];
top.left = v == null ? null : new TreeNode(v);
if (index < n) {let v = array[index++];
top.right = v == null ? null : new TreeNode(v);
}
if (top.left) queue.push(top.left);
if (top.right) queue.push(top.right);
}
return root;
}
/**
* 层序遍历一棵二叉树 生成一个数组
* @param {TreeNode} root
* @return {any[]}
*/
function getLayerOrderArrayFromTree(root) {let res = [];
let que = [root];
while (que.length) {
let len = que.length;
for (let i = 0; i < len; i++) {let cur = que.shift();
if (cur) {res.push(cur.val);
que.push(cur.left, cur.right);
} else {res.push(null);
}
}
}
while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null
return res;
}
一个例子，@leetcode 110，判断一棵二叉树是不是均衡二叉树。
/** * @param {TreeNode} root * @return {boolean} */
var isBalanced = function(root) {if (!root) return true; // 认为空指针也是均衡树吧
// 获取一个二叉树的深度
const d = (root) => {if (!root) return 0;
return _max(d(root.left), d(root.right)) + 1;
}
let leftDepth = d(root.left);
let rightDepth = d(root.right);
// 深度差不超过 1 且子树都是均衡树
if (_min(leftDepth, rightDepth) + 1 >= _max(leftDepth, rightDepth)
&& isBalanced(root.left) && isBalanced(root.right)) return true;
return false;
};
log(isBalanced(getTreeFromLayerOrderArray([3,9,20,null,null,15,7])));
log(isBalanced(getTreeFromLayerOrderArray([1,2,2,3,3,null,null,4,4])));
二分查找
参考 C++ STL 中的 lower_bound 和 upper_bound。这两个函数真的很好用的！
/** * 寻找 >=target 的最小下标 * @param {number[]} nums
* @param {number} target
* @return {number} */
function lower_bound(nums, target) {
let first = 0;
let len = nums.length;
while (len > 0) {
let half = len >> 1;
let middle = first + half;
if (nums[middle] < target) {
first = middle + 1;
len = len - half - 1;
} else {len = half;}
}
return first;
}
/** * 寻找 >target 的最小下标 * @param {number[]} nums
* @param {number} target
* @return {number} */
function upper_bound(nums, target) {
let first = 0;
let len = nums.length;
while (len > 0) {
let half = len >> 1;
let middle = first + half;
if (nums[middle] > target) {len = half;} else {
first = middle + 1;
len = len - half - 1;
}
}
return first;
}
照例，举个例子，@leetcode 34。题意是给一个排好序的数组和一个指标数字，求数组中等于指标数字的元素最小下标和最大下标。不存在就返回 -1。
/** * @param {number[]} nums
* @param {number} target
* @return {number[]} */
var searchRange = function(nums, target) {let lower = lower_bound(nums, target);
let upper = upper_bound(nums, target);
let size = nums.length;
// 不存在返回 [-1, -1]
if (lower >= size || nums[lower] !== target) return [-1, -1];
return [lower, upper - 1];
};
在 VS Code 中刷 LeetCode
后面说的那些模板，难道每一次关上新的一道题都要复制一遍么？当然不必啦。
首先配置代码片段 抉择 Code -> Preferences -> User Snippets，而后抉择 JavaScript
而后把文件替换为上面的代码：
{
"leetcode template": {
"prefix": "@lc",
"body": ["const _max = Math.max.bind(Math);","const _min = Math.min.bind(Math);","const _pow = Math.pow.bind(Math);","const _floor = Math.floor.bind(Math);","const _round = Math.round.bind(Math);","const _ceil = Math.ceil.bind(Math);","const log = console.log.bind(console);","// const log = _ => {}","/**************** 链表 ****************/","/**","* 链表节点","* @param {*} val","* @param {ListNode} next","*/","function ListNode(val, next = null) {","this.val = val;","this.next = next;","}","/**","* 将一个数组转为链表","* @param {array} array","* @return {ListNode}","*/","const getListFromArray = (array) => {","let dummy = new ListNode()","let pre = dummy;","array.forEach(x => pre = pre.next = new ListNode(x));","return dummy.next;","}","/**","* 将一个链表转为数组","* @param {ListNode} list","* @return {array}","*/","const getArrayFromList = (list) => {","let a = [];","while (list) {","a.push(list.val);","list = list.next;","}","return a;","}","/**","* 打印一个链表","* @param {ListNode} list","*/","const logList = (list) => {","let str ='list: ';","while (list) {","str += list.val +'->';","list = list.next;","}","str +='end';","log(str);","}","/**************** 矩阵（二维数组）****************/","/**","* 初始化一个二维数组","* @param {number} r 行数","* @param {number} c 列数","* @param {*} init 初始值","*/","const initMatrix = (r, c, init = 0) => new Array(r).fill().map(_ => new Array(c).fill(init));","/**","* 获取一个二维数组的行数和列数","* @param {any[][]} matrix","* @return [row, col]","*/","const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length];","/**","* 遍历一个二维数组","* @param {any[][]} matrix","* @param {Function} func","*/","const matrixFor = (matrix, func) => {","matrix.forEach((row, i) => {","row.forEach((item, j) => {","func(item, i, j, row, matrix);","});","})","}","/**","* 获取矩阵第 index 个元素 从 0 开始","* @param {any[][]} matrix","* @param {number} index","*/","function getMatrix(matrix, index) {","let col = matrix[0].length;","let i = ~~(index / col);","let j = index - i * col;","return matrix[i][j];","}","/**","* 设置矩阵第 index 个元素 从 0 开始","* @param {any[][]} matrix","* @param {number} index","*/","function setMatrix(matrix, index, value) {","let col = matrix[0].length;","let i = ~~(index / col);","let j = index - i * col;","return matrix[i][j] = value;","}","/**************** 二叉树 ****************/","/**","* 二叉树节点","* @param {*} val","* @param {TreeNode} left","* @param {TreeNode} right","*/","function TreeNode(val, left = null, right = null) {","this.val = val;","this.left = left;","this.right = right;","}","/**","* 通过一个档次遍历的数组生成一棵二叉树","* @param {any[]} array","* @return {TreeNode}","*/","function getTreeFromLayerOrderArray(array) {","let n = array.length;","if (!n) return null;","let index = 0;","let root = new TreeNode(array[index++]);","let queue = [root];","while(index < n) {","let top = queue.shift();","let v = array[index++];","top.left = v == null ? null : new TreeNode(v);","if (index < n) {","let v = array[index++];","top.right = v == null ? null : new TreeNode(v);","}","if (top.left) queue.push(top.left);","if (top.right) queue.push(top.right);","}","return root;","}","/**","* 层序遍历一棵二叉树 生成一个数组","* @param {TreeNode} root","* @return {any[]}","*/","function getLayerOrderArrayFromTree(root) {","let res = [];","let que = [root];","while (que.length) {","let len = que.length;","for (let i = 0; i < len; i++) {","let cur = que.shift();","if (cur) {","res.push(cur.val);","que.push(cur.left, cur.right);","} else {","res.push(null);","}","}","}","while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null","return res;","}","/**************** 二分查找 ****************/","/**","* 寻找 >=target 的最小下标","* @param {number[]} nums","* @param {number} target","* @return {number}","*/","function lower_bound(nums, target) {","let first = 0;","let len = nums.length;",""," while (len > 0) {"," let half = len >> 1;"," let middle = first + half;"," if (nums[middle] < target) {"," first = middle + 1;"," len = len - half - 1;","} else {"," len = half;","}"," }"," return first;","}","","/**","* 寻找 >target 的最小下标","* @param {number[]} nums","* @param {number} target","* @return {number}","*/","function upper_bound(nums, target) {","let first = 0;","let len = nums.length;",""," while (len > 0) {"," let half = len >> 1;"," let middle = first + half;"," if (nums[middle] > target) {"," len = half;","} else {"," first = middle + 1;"," len = len - half - 1;","}"," }"," return first;","}","$1"],"description":"LeetCode 罕用代码模板 "
}
}
当前每一次写题之前，键入 @lc 就会呈现提醒，轻松退出代码模板。