排序

桶排序

是计数排序的升级版，利用了函数的映射关系

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的N个数据均匀分配到K个桶中

最快：输入的数据可以均匀分配到每一个桶中
最慢：输入的数据被分配到了一个桶中

构建 大/小 根堆

  1. class Heap {
  2.     constructor(comparator) {
  3.         this.size = 0
  4.         this.values = []
  5.         // 如果是 (a - b) -> 小根堆
  6.         // 如果是 (b - a) -> 大根堆
  7.         this.comparator = comparator || Heap.minComparator
  8.     }
  10.     add(val) {
  11.         this.values[this.size++] = val
  12.         this.bubbleUp()
  13.     }
  15.     peak() {
  16.         return this.values[0] || null
  17.     }
  19.     poll() {
  20.         const ret = this.values[0]
  21.         const end = this.values.pop()
  22.         this.size--
  23.         if (this.values.length) {
  24.             this.values[0] = end
  25.             this.bubbleDown()
  26.         }
  27.         return ret
  28.     }
  30.     // 上浮
  31.     bubbleUp() {
  32.         let index = this.values.length - 1
  33.         let parent = (index - 1) >> 1
  35.         while (this.comparator(this.values[index], this.values[parent]) < 0) {
  36.             this.swap(parent, index)
  37.             index = parent
  38.             parent = (index - 1) >> 1
  39.         }
  40.     }
  42.     bubbleDown() {
  43.         let index = 0,
  44.             len = this.values.length
  46.         while (true) {
  47.             let left = null,
  48.                 right = null,
  49.                 swap = null,
  50.                 leftIndex = index * 2 + 1, // 左子节点
  51.                 rightIndex = index * 2 + 2 // 右子节点
  52.             if (leftIndex < len) {
  53.                 left = this.values[leftIndex]
  54.                 if (this.comparator(left, this.values[index]) < 0) {
  55.                     swap = leftIndex
  56.                 }
  57.             }
  59.             if (rightIndex < len) {
  60.                 right = this.values[rightIndex]
  61.                 if (swap !== null && this.comparator(right, left) < 0) {
  62.                     swap = rightIndex
  63.                 }
  64.             }
  66.             if (swap === null) break
  68.             this.swap(index, swap)
  69.             index = swap
  70.         }
  71.     }
  73.     swap(i, j) {
  74.         ;[this.values[i], this.values[j]] = [this.values[j], this.values[i]]
  75.     }
  77.     size() {
  78.         return this.size
  79.     }
  80. }
  82. Heap.minComparator = (a, b) => a - b
  83. Heap.maxComparator = (a, b) => b - a

前 k 小的数

  1. let a = [] // 堆
  2. let n = 0 // 当前堆中的个数
  4. // 下沉
  5. const sink = function (i) {
  6.     let t = a[i] // 要下沉的元素
  7.     let j = 0 // 左子节点，i 节点的左子节点：(2 * i) + 1，右子节点：2 * i + 2
  8.     while ((j = i * 2 + 1) < n) {
  9.         // 找到 i 节点的左子节点
  10.         // 比插入排序多出来一步，需要在两个后继中找到最大的
  11.         // j < n - 1 表示存在右子节点
  12.         // 如果存在并且右子节点更大
  13.         // 就指向右子节点
  14.         if (j < n - 1 && a[j] < a[j + 1]) {
  15.             // 小根堆这里要改成大于
  16.             j = j + 1
  17.         }
  18.         // 如果子节点比t大
  19.         // t还需要向后排，把这个大的子节点移上去
  20.         if (a[j] > t) {
  21.             // 如果是小根堆，这里改成 小于 即可
  22.             a[i] = a[j]
  23.             i = j
  24.         } else {
  25.             // 找到了t的位置
  26.             // 此时t的位置是大于所有子节点的
  27.             break
  28.         }
  29.     }
  30.     // 将t的位置放在找到的位置那里
  31.     a[i] = t
  32. }
  34. // 上浮
  35. const swim = function (i) {
  36.     let t = a[i]
  37.     let par = 0 // 父节点, i 节点的父节点 (i - 1) / 2
  38.     while (i > 0 && (par = Math.floor((i - 1) / 2)) !== i) {
  39.         if (a[par] < t) {
  40.             // 如果是小根堆，这里改成 大于 即可
  41.             a[i] = a[par]
  42.             i = par
  43.         } else {
  44.             break
  45.         }
  46.     }
  47.     a[i] = t
  48. }
  50. // 新来的元素先上浮，然后再执行上浮操作
  51. const heapPush = function (v) {
  52.     a[n++] = v
  53.     swim(n - 1)
  54. }
  56. // 返回a[0]，因为是队列
  57. // 将最后一个元素放到第一个位置
  58. // 然后下沉
  59. const heapPop = function () {
  60.     let ret = a[0]
  61.     a[0] = a[--n]
  62.     sink(0)
  63.     return ret
  64. }
  66. const size = () => {
  67.     return n
  68. }

BFPRT 算法

数组中第 k 小的数

  1. function getMinKthByBFPRT(arr, k) {
  2.     let copyArr = arr.slice()
  3.     return bfprt(copyArr, 0, copyArr.length - 1, copyArr.length - k)
  4. }
  5. // BFPRT 算法模板
  6. function bfprt(arr, begin, end, i) {
  7.     if (begin === end) {
  8.         return arr[begin]
  9.     }
  10.     // 找到划分依据
  11.     let pivot = medianOfMedians(arr, begin, end)
  12.     // partition根据这个值分，不是随机的
  13.     let pivotRange = partition(arr, begin, end, pivot)
  14.     // 根据范围继续partition
  15.     if (i >= pivotRange[0] && i <= pivotRange[1]) {
  16.         return arr[i]
  17.     } else if (i < pivotRange[0]) {
  18.         return bfprt(arr, begin, pivotRange[0] - 1, i)
  19.     } else {
  20.         return bfprt(arr, pivotRange[1] + 1, end, i)
  21.     }
  22. }
  24. // 求每个分组后的中位数组成的数组的中位数
  25. function medianOfMedians(arr, begin, end) {
  26.     // 5个分为一组，不足5个的单独为一组
  27.     let num = end - begin + 1
  28.     let offset = num % 5 === 0 ? 0 : 1
  29.     let len = Math.floor(num / 5) + offset
  30.     let medianArr = new Array(len).fill(null) // 中位数组成的数组
  31.     for (let i = 0; i < medianArr.length; i++) {
  32.         let beginI = begin + i * 5 // 分组后的每个数组的开头位置
  33.         let endI = beginI + 4 // 分组后的每个数组的结尾位置
  34.         medianArr[i] = getMedian(arr, beginI, Math.min(end, endI))
  35.     }
  36.     // 递归找到中位数数组里的中位数
  37.     return bfprt(medianArr, 0, medianArr.length - 1, Math.floor(medianArr.length / 2))
  38. }
  40. // 求一个数组的中位数
  41. function getMedian(arr, begin, end) {
  42.     insertionSort(arr, begin, end) // 排序
  43.     const mid = Math.ceil((end - begin) / 2) + begin
  44.     return arr[mid]
  45. }
  47. function insertionSort(arr, begin, end) {
  48.     for (let i = begin + 1; i <= end; i++) {
  49.         for (let j = i; j > begin; j--) {
  50.             if (arr[j - 1] > arr[j]) {
  51.                 swap(arr, j, j - 1)
  52.             } else {
  53.                 break
  54.             }
  55.         }
  56.     }
  57. }
  59. function partition(arr, begin, end, pivotValue) {
  60.     let small = begin - 1
  61.     let cur = begin
  62.     let big = end + 1
  63.     while (cur !== big) {
  64.         // 降序这里改成大于
  65.         if (arr[cur] < pivotValue) {
  66.             swap(arr, ++small, cur++)
  67.         }
  68.         // 降序这里改成小于
  69.         else if (arr[cur] > pivotValue) {
  70.             swap(arr, --big, cur)
  71.         } else {
  72.             cur++
  73.         }
  74.     }
  75.     return [small + 1, big - 1]
  76. }
  78. function swap(arr, a, b) {
  79.     ;[arr[a], arr[b]] = [arr[b], arr[a]]
  80. }

马拉车算法

最长回文子串
来到 i 位置

  1. 可能性 1：i 不在回文右边界里，暴力扩

  2. 可能性 2：i 在回文有边界里

    1. i 的对称位置的回文在 L，R 内
    2. i 的对称位置的回文在 L，R 外

    3. i 的对称位置的回文左边界与 L 压线，从 R 的右边开始扩

      1. var longestPalindrome = function (s) {
      2. const n = s.length
      3. if (n === 0) return ''
      4. let newStr = '#'
      5. // 构建新字符串，每个字符串被#包夹
      6. // #a#b#c#
      7. for (let i = 0; i < n; i++) {
      8.   newStr += s[i]
      9.   newStr += '#'
      10. }
      11. // 马拉车
      12. const N = newStr.length
      13. let arr = [] // 记录每个位置的回文最大半径
      14. let right = -1, // right->回文的最右边界
      15.   j = -1 // j->最大回文的中心点
      16. let start = 0, // start->回文开始的位置
      17.   end = -1 // end->回文结束的位置
      19. for (let i = 0; i < N; i++) {
      20.   let curArmLen // 当前位置构成的回文的最大半径
      21.   // i 在回文右边界内
      22.   if (right >= i) {
      23.       const curSymmetry = 2 * j - i // 当前位置关于上一个回文中心的对称点
      24.       const minArmLen = Math.min(arr[curSymmetry], right - i)
      25.       curArmLen = expand(newStr, i - minArmLen, i + minArmLen)
      26.   }
      27.   // i在回文右边界外
      28.   else {
      29.       curArmLen = expand(newStr, i, i)
      30.   }
      31.   arr.push(curArmLen)
      33.   // 找到了更大的回文子串
      34.   if (i + curArmLen > right) {
      35.       j = i // 更新最大回文中心点
      36.       right = i + curArmLen // 更新回文的最右边界
      37.   }
      39.   // 当前的回文长度大于了之前的回文长度
      40.   // 更新回文开始的位置, 回文结束的位置
      41.   if (curArmLen * 2 + 1 > end - start) {
      42.       start = i - curArmLen
      43.       end = i + curArmLen
      44.   }
      45. }
      46. // 到这里我们得到的 [start, end] 就是最大回文字符串了
      47. let ans = ''
      48. for (let i = start; i <= end; i++) {
      49.   if (newStr[i] !== '#') {
      50.       ans += newStr[i]
      51.   }
      52. }
      54. return ans
      56. // 找出回文最大半径
      57. // 暴力扩
      58. function expand(s, left, right) {
      59.   while (left >= 0 && right < s.length && s[left] === s[right]) {
      60.       --left
      61.       ++right
      62.   }
      63.   return (right - left - 2) / 2
      64. }
      65. }

KMP 算法

实现 strStr

  1. var strStr = function (str1, str2) {
  2.     const n = str1.length,
  3.         m = str2.length
  5.     if (m === 0) return 0
  7.     const next = getNext(str2)
  9.     let i = 0,
  10.         j = 0
  11.     while (i < str1.length && j < str2.length) {
  12.         if (str1[i] == str2[j]) {
  13.             i++
  14.             j++
  15.         } else {
  16.             if (next[j] == -1) {
  17.                 i++
  18.             } else {
  19.                 j = next[j]
  20.             }
  21.         }
  22.     }
  23.     return j == str2.length ? i - j : -1
  24. }
  26. const getNext = str => {
  27.     if (str.length == 1) {
  28.         return [-1]
  29.     }
  30.     const next = Array(str.length)
  31.     next[0] = -1
  32.     next[1] = 0
  33.     let cn = 0
  34.     let i = 2
  35.     while (i < str.length) {
  36.         if (str[i - 1] == str[cn]) {
  37.             next[i++] = ++cn
  38.         } else if (cn > 0) {
  39.             cn = next[cn]
  40.         } else {
  41.             next[i++] = 0
  42.         }
  43.     }
  44.     return next
  45. }

相加

大数相加

字符串相加

  1. function add(num1, num2) {
  2.     let maxlen = Math.max(num1.length, num2.length)
  3.     let a = num1.padStart(maxlen, 0)
  4.     let b = num2.padStart(maxlen, 0)
  5.     let res = ''
  6.     let next = 0 //用一个变量存每一次的进位
  7.     for (let i = maxlen - 1; i >= 0; i--) {
  8.         let acc = Number(a[i]) + Number(b[i]) + next
  9.         next = Math.floor(acc / 10)
  10.         res = (acc % 10) + res
  11.     }
  12.     if (next === 1) res = '1' + res //如果到最高位还有进位就再加一位
  13.     return res
  14. }

小数相加

  1. add(num1,num2){
  2.   let len1 = (num1 + "").split(".")[1].length;
  3.   let len2=(num2 + "").split(".")[1].length;
  4.   let maxlen = Math.max(len1, len2);
  5.   let a = Math.pow(10, maxlen);
  6.   return (num1 * a + num2 * a) / a;
  7. }

栈

单调栈

  1. function findRightSmall(arr) {
  2.     let ans = []
  3.     let t = [] // 存放下标
  4.     for (let i = 0; i < arr.length; i++) {
  5.         while (t.length && arr[t.length - 1] > arr[i]) {
  6.             ans[t[t.length - 1]] = i
  7.             t.pop()
  8.         }
  9.         t.push(i)
  10.     }
  11.     while (t.length) {
  12.         ans[t[t.length - 1]] = -1
  13.         t.pop()
  14.     }
  15.     return ans
  16. }

FIFO 队列与单调队列

循环队列

取模技巧

  • index = i 的后一个 == (i + 1) % capacity

  • index = i 的前一个 == (i - 1 + capacity) % capacity

    1. class MyCircularQueue {
    2.   constructor(k) {
    3.       this.capacity = k + 1
    4.       this.a = Array(k + 1)
    5.       this.front = 0
    6.       this.rear = 0 
    7.   }
    8.   enQueue(value) {
    9.       if (this.isFull()) {
    10.           return false
    11.       }
    12.       this.a[this.rear] = value // 元素放在rear(队尾)位置
    13.       this.rear = (this.rear + 1) % this.capacity // rear向后移动
    14.       return true
    15.   }
    17.   deQueue() {
    18.       if (this.isEmpty()) {
    19.           return false
    20.       }
    21.       this.front = (this.front + 1) % this.capacity
    22.       return true
    23.   }
    25.   Front() {
    26.       return this.isEmpty() ? -1 : this.a[this.front]
    27.   }
    29.   Rear() {
    30.       let tail = (this.rear - 1 + this.capacity) % this.capacity
    31.       return this.isEmpty() ? -1 : this.a[tail]
    32.   }
    34.   isEmpty() {
    35.       return this.front === this.rear
    36.   }
    38.   isFull() {
    39.       return (this.rear + 1) % this.capacity === this.front
    40.   }
    41. }

单调队列

  1. class MonoMinusQueue {
  2.   constructor() {
  3.     this.Q = []
  4.   }
  5.   push(val) {
  6.     while (this.Q.length && this.Q[this.Q.length - 1] < val) {
  7.       this.Q.pop()
  8.     }
  9.     this.Q.push(val)
  10.   }
  11.   pop(val) {
  12.     if (this.Q.length && this.Q[0] === val) {
  13.       this.Q.shift()
  14.     }
  15.   }
  16. }

二叉树的遍历

前序遍历

  1. function preorderTraversal(root) {
  2.     const stack = []
  3.     const ans = []
  4.     while (root !== null || stack.length) {
  5.         while (root !== null) {
  6.             stack.push(root)
  7.             ans.push(root.val)
  8.             root = root.left
  9.         }
  10.         root = s.pop()
  11.         root = root.right
  12.     }
  13.     return ans
  14. }

中序遍历

  1. function inorderTraversal(root) {
  2.     const stack = []
  3.     const ans = []
  4.     while (root !== null || stack.length) {
  5.         while (root !== null) {
  6.             stack.push(root)
  7.             root = root.left
  8.         }
  9.         root = s.pop()
  10.     ans.push(root.val)
  11.         root = root.right
  12.     }
  13.     return ans
  14. }

后序遍历

  1. function inorderTraversal(root) {
  2.     const stack = []
  3.     const ans = []
  4.     let pre = null
  5.     while (stack.length && root !== null) {
  6.         while (root !== null) {
  7.             stack.push(root)
  8.             root = root.left
  9.         }
  10.         root = stack[stack.length - 1]
  11.         if (root.right === null || root.right === pre) {
  12.             ans.push(root.val)
  13.             stack.pop()
  14.             pre = root
  15.             root = null
  16.         } else {
  17.             root = root.right
  18.         }
  19.     }
  20.     return ans
  21. }

Morris 遍历

  1. 如果 cur 无左孩子，cur 向右移动(cur = cur.right)
  2. 如果 cur 有左孩子，找到 cur 左子树上最右的节点，记为 mostright
    1. 如果 mostright 的 right 指针指向空，让其指向 cur，cur 向左移动(cur = cur.left)
    2. 如果 mostright 的 right 指针指向 cur，让其指向空，cur 向右移动(cur = cur.right)

并查集

  1. let F = null
  2. let count = 0
  3. let Cnt = null
  4. function init(n) {
  5.     F = Array(n)
  6.     Cnt = Array(n)
  7.     for (let i = 0; i < n; i++) {
  8.         F[i] = i
  9.         Cnt[i] = i
  10.     }
  11.     count = n
  12. }
  13. function find(x) {
  14.     return x === F[x] ? x : find(F[x])
  15. }
  16. function union(x, y) {
  17.     let xpar = find(x)
  18.     let ypar = find(y)
  19.     if (xpar !== ypar) {
  20.         F[xpar] = ypar
  21.         Cnt[ypar] += Cnt[xpar]
  22.         count--
  23.     }
  24. }
  25. function size(i) {
  26.     return Cnt[find(i)]
  27. }

二分

左闭右开原则

  1. function lowerBound(arr, target) {
  2.   let l = 0, r = arr.length
  3.   while (l < r) {
  4.     let m = (l + r) >> 1
  5.     if (arr[m] < target) {
  6.       l = m + 1
  7.     } else {
  8.       r = m
  9.     }
  10.   }
  11.   return l
  12. }

双指针

区间单调性

不允许出现 满足条件 =》不满足条件 =》满足条件 的情况

区间最优原则

从左向右遍历区间右端固定集合中的每个区间，找到一个满足条件的解即可
再添加一个左指针 left，指向区间的左边，与A[i] 元素构成区间 (left, i]。—— 开闭原则（左开右闭）
寻找A[i] 为右边界的最优解可以分为3步走：

  1. 将 A[i] 加到区间中，形成新区间 (left, i]

  2. 遍历 A[i] 的区间右端固定集合，直到找到以 A[i] 为右端点的最优解

    1. while (left < i && (left, i] 区间不满足要求) {
    2. left++;
    3. }

  3. (left, i] 满足要求

最长区间时双指针的结论：最长区间问题的最优解 =》只需要遍历每个元素 A[i] 的最优解

最长区间

题目具备如下特点：

  • 给定一个条件
  • 求最长区间/最长子串
  • 题目给的区间需要具备单调性

解题：

  1. 两个指针：left 指针和 right 指针，两个指针形成的区间 (left, right]。左开右闭
  2. 惰性原则：left 直到条件不满足的时候才向右移动
    1. function maxLength(arr) {
    2. let n = arr.length;
    3. let left = -1;
    4. let ans = 0;
    5. for (let i = 0; i < n; i++) {
    6.  // 1. 将 arr[i] 加入区间中，形成(left, i]
    7.  // 2. 将 arr[i] 加入后，惰性原则
    8.  while (check((left, i])/* 检查区间状态是否满足条件*/ ) {
    9.    ++left; // 如果不满足条件移动左指针
    10.    // 修改区间的状态
    11.  }
    12.  ans = max(ans, i - left);
    13. }
    14. return ans;
    15. }
    无重复最长子串