转载链接

位运算的一些小技巧

判断一个整数 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;
}

在 VS Code 中刷 LeetCode

前面说的那些模板，难道每一次打开新的一道题都要复制一遍么？当然不用啦。
首先配置代码片段 选择 Code -> Preferences -> User Snippets ，然后选择 JavaScript

在文件中插入代码

  1. 复制代码
  2. {
  3.   "leetcode template": {
  4.     "prefix": "@lc",
  5.     "body": [
  6.       "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;","}",
  7.       "$1"
  8.     ],
  9.     "description": "LeetCode常用代码模板"
  10.   }
  11. }

具体常用代码：

  1. const _max = Math.max.bind(Math);  
  2. const _min = Math.min.bind(Math);  
  3. const _pow = Math.pow.bind(Math);  //次方
  4. const _floor = Math.floor.bind(Math);  //向下取整
  5. const _round = Math.round.bind(Math);  //四舍五入
  6. const _ceil = Math.ceil.bind(Math);  //向上取整
  7. const log = console.log.bind(console);
  8. // const log = _ => {}
  9. //注：第八行将log赋值给空函数是为了注释掉后面所有的log
  10. /**************** 链表 ****************/
  11. /**
  12.  * 链表节点
  13.  * @param {*} val
  14.  * @param {ListNode} next
  15.  */
  16. function ListNode(val, next = null) {
  17.     this.val = val;
  18.     this.next = next;
  19. }
  20. /**
  21.  * 将一个数组转为链表
  22.  * @param {array} array
  23.  * @return {ListNode}
  24.  */
  25. const getListFromArray = (array) => {
  26.     let dummy = new ListNode()
  27.     let pre = dummy;
  28.     array.forEach(x => pre = pre.next = new ListNode(x));
  29.     return dummy.next;
  30. }
  31. /**
  32.  * 将一个链表转为数组
  33.  * @param {ListNode} list
  34.  * @return {array}
  35.  */
  36. const getArrayFromList = (list) => {
  37.     let a = [];
  38.     while (list) {
  39.         a.push(list.val);
  40.         list = list.next;
  41.     }
  42.     return a;
  43. }
  44. /**
  45.  * 打印一个链表
  46.  * @param {ListNode} list 
  47.  */
  48. const logList = (list) => {
  49.     let str = 'list: ';
  50.     while (list) {
  51.         str += list.val + '->';
  52.         list = list.next;
  53.     }
  54.     str += 'end';
  55.     log(str);
  56. }
  57. /**************** 矩阵（二维数组） ****************/
  58. /**
  59.  * 初始化一个二维数组
  60.  * @param {number} r 行数
  61.  * @param {number} c 列数
  62.  * @param {*} init 初始值
  63.  */
  64. const initMatrix = (r, c, init = 0) => new Array(r).fill().map(_ => new Array(c).fill(init));
  65. /**
  66.  * 获取一个二维数组的行数和列数
  67.  * @param {any[][]} matrix
  68.  * @return [row, col]
  69.  */
  70. const getMatrixRowAndCol = (matrix) => matrix.length === 0 ? [0, 0] : [matrix.length, matrix[0].length];
  71. /**
  72.  * 遍历一个二维数组
  73.  * @param {any[][]} matrix 
  74.  * @param {Function} func 
  75.  */
  76. const matrixFor = (matrix, func) => {
  77.     matrix.forEach((row, i) => {
  78.         row.forEach((item, j) => {
  79.             func(item, i, j, row, matrix);
  80.         });
  81.     })
  82. }
  83. /**
  84.  * 获取矩阵第index个元素 从0开始
  85.  * @param {any[][]} matrix 
  86.  * @param {number} index 
  87.  */
  88. function getMatrix(matrix, index) {
  89.     let col = matrix[0].length;
  90.     let i = ~~(index / col);
  91.     let j = index - i * col;
  92.     return matrix[i][j];
  93. }
  94. /**
  95.  * 设置矩阵第index个元素 从0开始
  96.  * @param {any[][]} matrix 
  97.  * @param {number} index 
  98.  */
  99. function setMatrix(matrix, index, value) {
  100.     let col = matrix[0].length;
  101.     let i = ~~(index / col);
  102.     let j = index - i * col;
  103.     return matrix[i][j] = value;
  104. }
  105. /**************** 二叉树 ****************/
  106. /**
  107.  * 二叉树节点
  108.  * @param {*} val
  109.  * @param {TreeNode} left
  110.  * @param {TreeNode} right
  111.  */
  112. function TreeNode(val, left = null, right = null) {
  113.     this.val = val;
  114.     this.left = left;
  115.     this.right = right;
  116. }
  117. /**
  118.  * 通过一个层次遍历的数组生成一棵二叉树
  119.  * @param {any[]} array
  120.  * @return {TreeNode}
  121.  */
  122. function getTreeFromLayerOrderArray(array) {
  123.     let n = array.length;
  124.     if (!n) return null;
  125.     let index = 0;
  126.     let root = new TreeNode(array[index++]);
  127.     let queue = [root];
  128.     while(index < n) {
  129.         let top = queue.shift();
  130.         let v = array[index++];
  131.         top.left = v == null ? null : new TreeNode(v);
  132.         if (index < n) {
  133.             let v = array[index++];
  134.             top.right = v == null ? null : new TreeNode(v);
  135.         }
  136.         if (top.left) queue.push(top.left);
  137.         if (top.right) queue.push(top.right);
  138.     }
  139.     return root;
  140. }
  141. /**
  142.  * 层序遍历一棵二叉树 生成一个数组
  143.  * @param {TreeNode} root 
  144.  * @return {any[]}
  145.  */
  146. function getLayerOrderArrayFromTree(root) {
  147.     let res = [];
  148.     let que = [root];
  149.     while (que.length) {
  150.         let len = que.length;
  151.         for (let i = 0; i < len; i++) {
  152.             let cur = que.shift();
  153.             if (cur) {
  154.                 res.push(cur.val);
  155.                 que.push(cur.left, cur.right);
  156.             } else {
  157.                 res.push(null);
  158.             }
  159.         }
  160.     }
  161.     while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null
  162.     return res;
  163. }
  164. /**************** 二分查找 ****************/
  165. /**
  166.  * 寻找>=target的最小下标
  167.  * @param {number[]} nums
  168.  * @param {number} target
  169.  * @return {number}
  170.  */
  171. function lower_bound(nums, target) {
  172.     let first = 0;
  173.     let len = nums.length;
  175.     while (len > 0) {
  176.         let half = len >> 1;
  177.         let middle = first + half;
  178.         if (nums[middle] < target) {
  179.             first = middle + 1;
  180.             len = len - half - 1;
  181.         } else {
  182.             len = half;
  183.         }
  184.     }
  185.     return first;
  186. }
  188. /**
  189.  * 寻找>target的最小下标
  190.  * @param {number[]} nums
  191.  * @param {number} target
  192.  * @return {number}
  193.  */
  194. function upper_bound(nums, target) {
  195.     let first = 0;
  196.     let len = nums.length;
  198.     while (len > 0) {
  199.         let half = len >> 1;
  200.         let middle = first + half;
  201.         if (nums[middle] > target) {
  202.             len = half;
  203.         } else {
  204.             first = middle + 1;
  205.             len = len - half - 1;
  206.         }
  207.     }
  208.     return first;
  209. }