位运算相关

判断奇数偶数

&以特定的方式组合操作二进制数中对应的位，如果对应的位都为1，那么结果就是1， 如果任意一个位是0 则结果就是0。

  1. // 0的二进制表示为: 00000000 00000000 00000000 00000000
  2. // 1的二进制表示为: 00000000 00000000 00000000 00000001
  3. // 2的二进制表示为: 00000000 00000000 00000000 00000010
  4. // 3的二进制表示为: 00000000 00000000 00000000 00000011
  5. // 4的二进制表示为: 00000000 00000000 00000000 00000100
  7. funciton isOdd(n) {
  8.     return n & 1 === 1;
  9. }

二分查找

  1. // 非递归版本
  2. function binarySearch(nums, target) {
  3.     let low = 0;
  4.     let high = nums.length - 1;
  6.     while(low <= high) {
  7.       let mid = parseInt((low + high) / 2);
  8.       if(nums[mid] === target) {
  9.         return mid;
  10.       }
  11.       if(nums[mid] > target) {
  12.         high = mid - 1;
  13.       }
  14.       if(nums[mid] < target) {
  15.         low = mid + 1;
  16.       }
  17.     }
  18.     return -1;
  19.   }
  21. // 递归
  22. function binarySearch(nums, target) {
  23.     let low = 0;
  24.     let high = nums.length -1;
  25.     const binaryWalker = (nums, low, high, target) => {
  26.       if(low > high) return -1;
  27.       const mid = parseInt((low + high) / 2);
  28.       if(nums[mid] === target) return mid;
  29.       if(nums[mid] > target) return binaryWalker(nums, low, mid - 1, target);
  30.       if(nums[mid] < target) return binaryWalker(nums, low + 1, high, target);
  31.     }
  32.     return binaryWalker(nums, low, high, target);
  34.   }

常见排序

冒泡

  1. function bubbleSort(arr) {
  2.     let i = arr.length - 1;
  3.     while(i >= 0) {
  4.       for(let j = 0; j < i; j++) {
  5.         if(arr[j] > arr[j + 1]) {
  6.           [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
  7.         }
  8.       }
  9.       i--;
  10.     }
  11.     return arr;
  12.   }

快排

  1. function quickSort(arr) {
  2.     if(arr.length <= 1) return arr;
  4.     let left = [];
  5.     let right = [];
  7.     let pivot = arr[0];
  9.     for(let i = 1; i < arr.length; i++) {
  10.       if(arr[i] >= pivot) {
  11.         right.push(arr[i]);
  12.       } else {
  13.         left.push(arr[i]);
  14.       }
  15.     }
  17.     return [...quickSort(left), pivot, ...quickSort(right)];
  18.   }

二叉树遍历相关

先序遍历（中->左->右）

  1. // 递归实现
  2. function preOrderTraverse(root) {
  3.     if(root) {
  4.       console.log(root);
  5.       preOrderTraverse(root.left);
  6.       preOrderTraverse(root.right);
  7.     }
  8.   }
  9. // 非递归实现
  10. function preOrderTraverse(root) {
  11.     let stack = [];
  13.     if(root) {
  14.       stack.push(root);
  15.     }
  17.     while(stack.length) {
  18.       let temp = stack.pop();
  19.       console.log(temp);
  21.       if(temp.right) stack.push(temp.right);
  23.       if(temp.left) stack.pus(temp.left);
  24.     }
  25.   }

层次遍历

  1. function levelTraverse(root) {
  2.     if(!root) return;
  3.     let stack = [];
  4.     stack.push(root);
  6.     while(stack.length) {
  7.       let temp = stack.shift();
  8.       console.log(temp);
  9.       if(temp.left) stack.push(temp.left);
  10.       if(temp.right) stack.push(temp.right);
  11.     }
  12.   }