湖北省住房和建设厅网站首页,佛山用户网站建设,老牌网站建,北京品牌网站设计虽然很多人都觉得前端算法弱#xff0c;但其实 JavaScript 也可以刷题啊#xff01;最近两个月断断续续刷完了 leetcode 前 200 的 middle hard #xff0c;总结了一些刷题常用的模板代码。
常用函数
包括打印函数和一些数学函数。
const _max Math.max.bind(Math);
co…虽然很多人都觉得前端算法弱但其实 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赋值为空函数就可以了。
举一个简单的例子下面的代码是可以直接提交的。
// 计算 12...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 ^ n1 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; // 同 nfloor(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(); // 删掉结尾的 nullreturn 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 就会出现提示轻松加入代码模板。
