乐趣区

关于leetcode:前端leetcde算法面试套路之堆

jiezi

注释 plus

堆是动静求极值的数据结构，所以当遇到须要一直取极值的时候，就能够思考用堆了

舒适提醒，倡议每一道题都本人 new 一个堆，这样能力发现堆之美，其实就是不会再次遇到 topK 的时候只能用冒泡来做。

行文至此也该完结了，如果有 10 个关注，那就更新一下下一 part，dp 或者树吧，thx。

二叉堆的创立

剖析 — 小顶堆

  1. 这里是一个小顶堆，特点就是根节点的值比子节点的值都小，通常用作经典的前 K 大

  2. 次要有两个办法，

    • 一个是回升，这里次要用作构建堆的时候，整顿堆用的
    • 一个是下沉，这里次要用于弹出堆顶元素后，置换了堆顶值之后应用的，这里用到 this.data[0]，是因为这个办法个别是构建残缺的堆之后，才会应用
  3. 其余的办法不是不能够，只是为了保障灵活性，临时就先做个简易版，前面再思考，因为办法越多，其实兼容性就越差了
class MinHeap {constructor(len) {this.data = [];
      this.data[0] = len; // 第一个节点用来寄存堆的大小 -- 某些特定环境比拟好用
    }

    // 下浮
    down(index) {const size = this.data[0];
      while (index << 1 <= size) {
        let child = index << 1;

        if (child !== size && this.data[child] > this.data[child + 1]) {child += 1; // 如果右节点更小，就右节点作为下一个接盘的节点}
        if (this.data[index] > this.data[child]) {
          //   替换一下
          [this.data[index], this.data[child]] = [this.data[child],
            this.data[index],
          ];
          index = child;
        } else {
          //   只有其中一次生效了，那么就没必要持续往下查找了
          break;
        }
      }
    }

    // 都是从最底层开始算的
    upper() {// 这里不必 this.data[0] 是因为以后构建的堆可能还没达到堆的最大值，所以不能应用  
      let index = this.data.length - 1;
      while (index >> 1 > 0) {
        let father = index >> 1;
        if (this.data[index] < this.data[father]) {
          // 子节点比父节点要小，则网上走
          [this.data[index], this.data[father]] = [this.data[father],
            this.data[index],
          ];
          index = father;
        } else {break;}
      }
    }
  }

剖析 — 大顶堆

  • 绝对于初始版的小顶堆，这一版的大顶堆增加了两个办法，pop 和 add
  • add 办法能够写在应用堆的地位，然而为了让它和堆的第一个值匹配，所以写在了类办法外面，不便对 size 的增加
  • pop 是为了取出堆顶元素，堆是为了解决动静取极值 而存在的数据结构，所以必然要取出整顿的过程。
class MaxHeap {constructor() {this.data = [];
    this.data[0] = 0; // 第一个值是以后堆的 size
  }

  down(index) {
    const len = this.data.length; // 是下标极限
    while (index << 1 < len) {
      let child = index << 1;
      if (child !== len && this.data[child + 1] > this.data[child]) {child++;}
      if (this.data[child] > this.data[index]) {[this.data[child], this.data[index]] = [this.data[index],
          this.data[child],
        ];
        index = child;
      } else {break;}
    }
  }

  upper() {let index = this.data[0]; // 最大下标
    while (index >> 1 > 0) {
      const father = index >> 1;
      if (this.data[index] > this.data[father]) {[this.data[father], this.data[index]] = [this.data[index],
          this.data[father],
        ];
        index = father;
      } else {break;}
    }
  }

  add(value) {
    // 先加在最开端
    this.data.push(value);
    this.data[0]++; // size 也加一下
    this.upper(); // 整顿一下}

  // 弹出堆顶元素
  pop() {const last = this.data[0];
    [this.data[1], this.data[last]] = [this.data[last], this.data[1]]; // 替换堆顶和堆尾的值
    const ret = this.data.pop();
    this.data[0]--;
    this.down(1); // 整顿
    return ret;
  }
}

参考视频：传送门

215. 数组中的第 K 个最大元素

剖析

  • 这是一道炒鸡经典的题，能够用冒泡，快排，其中最经典的办法，莫过于小顶堆求值 — 作为教材根本的题目
  • 这里求第 K 大，那么就是要保护一个 K 大的小顶堆，而后堆顶就是第 K 大
  • 而后遍历数组 nums，先初始化一个 K 大的小顶堆，而后剩下的值就和堆顶比拟；
  • 只有是值大过堆顶值的，那么间接把堆顶值替换掉，但这时，堆顶值就不肯定是小顶堆中的最小值了，所以须要向下 down 整顿一下小顶堆
  • 遍历完结后就失去一个小顶堆了，而后间接去堆顶元素就是第 K 大了；
  • 工夫复杂度: {O(N*L) — 其中 N 是数组大小，L 是二叉堆的层高，L 其实相对来说比拟小，所以复杂度能够说靠近线性
  • 空间复杂度: O(M) — 其中 M 是就是 K 值，因为要保护一个 K 大堆
// 215. 数组中的第 K 个最大元素

// MinHeap 就是下面的那个类

var findKthLargest = function (nums, k) {
    // 创立一个 K 大的小顶堆
    const minHeap = new MinHeap(k);
    const len = nums.length;
    for (let i = 0; i < len; i++) {if (i < k) {
        // 初始化堆
        minHeap.data.push(nums[i]);
        minHeap.upper();} else {
        // 这个时候开始思考是否要压到小顶堆中了
        // 因为保护的是一个 k 大的小顶堆，而目标是求第 k 大，所以只须要判断前面的值是否大于小顶堆的堆顶值，即可知道是否须要取代
        if (nums[i] > minHeap.data[1]) {minHeap.data[1] = nums[i];
          minHeap.down(1);
        }
      }
    }
    return minHeap.data[1]
  };

1046. 最初一块石头的分量

剖析 — 大顶堆

  1. 依照题目曾经，须要取出一组数组中的最大值和次大值，进行肯定运算后，会将计算值返回给数组，而后循环操作，直到数组长度最大为 1 时完结
  2. 所以就是动静取极值，能够思考用堆来解决
  3. 定义一个办法 pop，每次获取堆顶元素，并将大顶堆整顿好，定义方法 add 为为堆退出元素
  4. 这样每一次取出两个元素，返回 1 或 0 个元素，始终到堆元素小于 2 时完结，返回堆中的元素或 0
  5. 空间复杂度就是保护堆，所以是 O(N), 工夫复杂度 O(NlogN)
// 1046. 最初一块石头的分量

var lastStoneWeight = function (stones) {
    // 保护一个大顶堆
    const heap = new MaxHeap();
    for (let i = 0; i < stones.length; i++) {heap.add(stones[i]);
    }

    while (heap.data[0] > 1) {
      // 1. 每次取出两个最大值
      const first = heap.pop();
      const second = heap.pop();
      // 2. 相减，再放回去
      const temp = first - second;
      if (temp) {heap.add(temp);
      }
    }
     return heap.data[0] ? heap.data[1]:0
  };

  class MaxHeap {constructor() {this.data = [];
      this.data[0] = 0; // 第一个值是以后堆的 size
    }

    down(index) {
      const len = this.data.length; // 是下标极限
      while (index << 1 < len) {
        let child = index << 1;
        if (child !== len && this.data[child + 1] > this.data[child]) {child++;}
        if (this.data[child] > this.data[index]) {[this.data[child], this.data[index]] = [this.data[index],
            this.data[child],
          ];
          index = child;
        } else {break;}
      }
    }

    upper() {let index = this.data[0]; // 最大下标
      while (index >> 1 > 0) {
        const father = index >> 1;
        if (this.data[index] > this.data[father]) {[this.data[father], this.data[index]] = [this.data[index],
            this.data[father],
          ];
          index = father;
        } else {break;}
      }
    }

    add(value) {
      // 先加在最开端
      this.data.push(value);
      this.data[0]++; // size 也加一下
      this.upper(); // 整顿一下}

    // 弹出堆顶元素
    pop() {const last = this.data[0];
      [this.data[1], this.data[last]] = [this.data[last],
        this.data[1],
      ] // 替换堆顶和堆尾的值
      const ret = this.data.pop();
      this.data[0]--;
      this.down(1); // 整顿
      return ret
    }
  }

23. 合并 K 个升序链表

剖析 — 堆

  1. 这里次要是把链表当成是堆的一个元素，以链表头的值作为小顶堆创立的基点
  2. 这里要求失去是 K 个升序链表合并链表，我每次都获取 K 个链表中的最小值，而后放到我本人的链表中，最初失去的就是一个合并完的升序链表了
  3. 空间复杂度就是保护堆，所以是 O(N∗M), 其中 N 是 lists 的长度，M 是 链表的均匀长度
  4. 工夫复杂度: 取出值合并到新链表 — O(N∗M)
// 23. 合并 K 个升序链表

/** * @剖析 * 1. 以链表的表头值作为判断元素，创立小顶堆 */
 var mergeKLists = function(lists) {let emptyNode  = new ListNode() // 本人创立一个
    // 构建一个堆
    const minHeap = new MinHeap()
    for (let i = 0; i < lists.length; i++) {const head = lists[i];
        if(head){minHeap.add(head)
        }
    }
    let cur = emptyNode;
    while(minHeap.data[0]){cur.next =new ListNode(minHeap.pop()) 
        cur = cur.next
    }
    return emptyNode.next
};

class MinHeap {constructor(){this.data = []
        this.data[0] = 0
    }

    down(index){const lastIndex = this.data[0]
        while(index<<1 <= lastIndex){
            let child = index<<1
            if(child!== lastIndex && this.data[child+1].val<this.data[child].val){child++}
            if(this.data[child].val<this.data[index].val){[this.data[child],this.data[index]] = [this.data[index],this.data[child]]
                index = child
            }else{break}
        }
    }

    upper(){let index = this.data[0]
        while(index>>1 > 0){
            let father = index>>1
            // 以表头值作为判断根据
            if(this.data[father].val>this.data[index].val){
                // 替换的是整个链表
                [this.data[father],this.data[index]] = [this.data[index],this.data[father]]
                index = father
            }else{break}
        }
    }

    add(head){
        // 增加的是一个排好序的链表，this.data.push(head);
        this.data[0]++
        this.upper()}

    // 将堆顶链表的头部值取出之后，重新整理
    pop(){const ret = this.data[1].val
        this.data[1] = this.data[1].next
        if(!this.data[1]){
            // 链表为 undefined 了
            [this.data[1],this.data[this.data[0]]] = [this.data[this.data[0]],this.data[1]]
            this.data.pop()
            this.data[0]--
        }
        this.down(1) // 整顿
        return ret // 返回的是一个值
    }
}

剖析 — 分治

  1. 多个排序链表很难解决，那么两个排序好的链表合并呢？
  2. 将两个有序链表合成一个，而后放进 list 持续走，最初合成一个即可
  3. 用分治，如果超出 2 个链表，就拆分了解决，mergeKLists(arr) 最初失去的也是一个排序好的链表，所以每次能够离开治，而后最初 merge 治；
  4. 合并两个链表的工夫复杂度 O(N)，分治解决 M 个链表的复杂度为 O(logM) 所以 O(NlogM)，其中 N 是链表的长度，M 是链表的数量
/** * @剖析 * 1. 多个排序链表很难解决，那么两个排序好的链表合并呢？* 2. 将两个有序链表合成一个，而后放进 list 持续走，最初合成一个即可 * 3. 用分治，如果超出 2 个链表，就拆分了解决，mergeKLists(arr) 最初失去的也是一个排序好的链表，所以每次能够离开治，而后最初 merge 治；* 4. 合并两个链表的工夫复杂度 ${O(N)}$，分治解决 M 个链表的复杂度为 ${O(logM)}$ 所以 ${O(NlogM)}$，其中 N 是链表的长度，M 是链表的数量 */
 var mergeKLists = function(lists) {
     const len  =lists.length
     // return lists.reduce((prev,cur) => mergeTwoList(prev,cur)) // 间接 api 递推即可，然而复杂度更高
    // 用分治的形式能够将 N 的复杂度升高到 logN
    if(len<1) return null
    if(len === 1) return lists[0]
    if(len === 2) return mergeTwoList(lists[0],lists[1])
    const mid = len>>1
    return mergeTwoList(mergeKLists(lists.slice(0,mid)),mergeKLists(lists.slice(mid)))

};

// 合并两个有序链表
function mergeTwoList (list1,list2){const emptyNode = new ListNode()
    let cur =emptyNode
    while(list1 && list2){if(list1.val<list2.val){
            cur.next= list1
            list1 = list1.next
        }else{
            cur.next= list2
            list2 = list2.next
        }
        cur = cur.next 
        cur.next = null
    }
    if(list1) cur.next = list1
    if(list2) cur.next = list2
    return emptyNode.next
}

451. 依据字符呈现频率排序

剖析

  1. 既然是要依照呈现评率进行新组装，所以先遍历一次字符串，用 map 将字符和呈现频率作为一组 item 保存起来 — 工夫空间复杂度都是 O(N)
  2. 这个时候其实只有依照频率从到到小排列好，而后一一取出重装即可
  3. 这边是用堆排序, 然而 item 不再是简略的数字，而是一个数组 [key,value]，所以相应的办法微调即可
  4. 堆排是工夫复杂度:O(NlogN), 最终的空间复杂度是 O(N)
// 451. 依据字符呈现频率排序

var frequencySort = function (s) {
    let ret = "";
    if (!s) return s;
    const map = new Map();
    const heap = new MaxHeap();
    for (let i = 0; i < s.length; i++) {const item = s[i];
      if (map.has(item)) {map.set(item, map.get(item) + 1);
      } else {map.set(item, 1);
      }
    }
    // 退出堆中，元素值是 [key,value], 要用 value 来进行比对
    for (let item of map.entries()) {heap.add(item);
    }
    while (heap.data[0]) {const item = heap.pop();
      ret += item[0].repeat(item[1]);
    }
    return ret;
  };

  class MaxHeap {constructor() {this.data = [];
      this.data[0] = 0;
    }

    down(index) {const lastIndex = this.data[0]; // 最初一个值的下标值
      while (index << 1 <= lastIndex) {
        let child = index << 1;
        if (
          child !== lastIndex &&
          this.data[child + 1][1] > this.data[child][1]
        ) {child++;}
        if (this.data[child][1] > this.data[index][1]) {
          // 留神，item 是数组，所以用第二个值做比对，然而替换的是整个 item
          [this.data[child], this.data[index]] = [this.data[index],
            this.data[child],
          ];
          index = child;
        } else {break;}
      }
    }

    upper() {let index = this.data[0];
      while (index >> 1 > 0) {
        const father = index >> 1;
        if (this.data[father][1] < this.data[index][1]) {
          // 留神，item 是数组，所以用第二个值做比对，然而替换的是整个 item
          [this.data[father], this.data[index]] = [this.data[index],
            this.data[father],
          ];
          index = father;
        } else {break;}
      }
    }

    add(item) {this.data.push(item);
      this.data[0]++;
      this.upper();}

    pop() {[this.data[1], this.data[this.data[0]]] = [this.data[this.data[0]],
        this.data[1],
      ];
      this.data[0]--;
      const temp = this.data.pop();
      this.down(1)
      return temp
    }
  }

378. 有序矩阵中第 K 小的元素

剖析

  1. 这里就是 item 为数组的 bottomK，和失常的 top K 只是多了以数组作为元素的解决
  2. 应用堆排的时候，只须要整顿函数 down 和 upper 比对的时候弄一下就好了
  3. 不过有一个区别就是，这个 K 有可能大于二维数组的数组长度 Len(matrix), 所以不能间接创立一个 K 大大顶堆取堆顶，反而要将二维数组所有元素都编入到 Len 大小的小顶堆中，而后再取 K 次
  4. 这也阐明了 top K 这类题的两种堆解法，要不就是设置 K 大 / 小 的堆，而后一直用元素去代替，要不设置全副元素的堆，而后弹出 K 次值；
  5. 工夫 / 空间复杂度 O(NlogN)
// 378. 有序矩阵中第 K 小的元素

/** * @剖析 -- 第 K 小 * 1. 这里给的排好序的矩阵，那么能够用小顶堆将矩阵中元素转移到小顶堆中，每次从堆顶取值后整顿，取到第 K 个即可 */
var kthSmallest = function(matrix, k) {const minHeap = new MinHeap()
    for(let i = 0;i<matrix.length;i++){minHeap.add(matrix[i])
    }
    const ret = []
    while(--k){minHeap.pop()
    }
    return minHeap.pop()};

class MinHeap {constructor(){this.data = []
        this.data[0] = 0
    }

    down(index){const lastIndex = this.data[0]
        while(index<<1 <= lastIndex){
            let child = index << 1
            if(child!==lastIndex && this.data[child+1][0]< this.data[child][0]){child++}
            if(this.data[child][0]< this.data[index][0]){[this.data[child], this.data[index]] = [this.data[index], this.data[child]]
                index = child
            }else {break}
        }
    }

    upper() {let index = this.data[0]
        while(index >>1 > 0){
            let father = index >> 1 
            if(this.data[father][0]> this.data[index][0]){[this.data[father], this.data[index]] = [this.data[index], this.data[father]]
                index = father
            }else {break}
        }
    }

    add(item){this.data.push(item)
        this.data[0]++
        this.upper()}

    // 这里不是间接弹出 item，而只是弹出堆顶的第一个字母，而后再整顿
    pop(){const temp = this.data[1].shift()
        if(!this.data[1].length){
             // 数组空了
             this.data[1] = this.data[this.data[0]]
             this.data.pop()
             this.data[0]--
        }
        this.down(1)
        return temp
    }
}

const ret = kthSmallest([[1,5,9],[10,11,13],[12,13,15]],8)
console.log(ret)

1054. 间隔相等的条形码

剖析

  1. 为了保障两两不相等，那得保障数量最多的那个条码必须先排完，避免排完其余就省它自个儿了；
  2. 所以先用 map 存储所有条码值 (key) 和数量(value)
  3. 这个时候就和 1046. 最初一块石头的分量很像了;
  4. 然而还有一点区别，就是每次你取出最大的两块，都只能取走一份进行排列，而后就要把剩下的放回去，保障每一次取两个值都是最大；这就好比，咱们这道题是去磨石头，每次相互之间磨掉一层皮，每一次都要拿最初的石头去磨，而 1046. 最初一块石头的分量 是间接两个一砸就完结了；
  5. map 存储时，工夫复杂度和空间复杂度都是 O(N), N 是长度；堆排，这个算不进去了，大略也是 O(NlogN) 吧
// 1054. 间隔相等的条形码

var rearrangeBarcodes = function (barcodes) {
  // 1. 将条形码的值和数量用 map 存储起来
  const map = new Map();
  for (let i = 0; i < barcodes.length; i++) {const item = barcodes[i];
    if (map.has(item)) {map.set(item, map.get(item) + 1);
    } else {map.set(item, 1);
    }
  }
  // 2. 创立最大堆，进行堆排
  const heap = new MaxHeap();
  for (let item of map.entries()) {heap.add(item); // [key,value]
  }

  // 3. 每次取出最大的两个 item 进行重写排列
  const ret = [];
  while (heap.data[0] > 1) {
    // 这里是默认是保障存在答案，所以即使最初还有 item，那么对应的值也只有 1 个
    // 然而如果条件没有已知，那么就能够依据这个值进行判断是否胜利了
    const first = heap.pop();
    const second = heap.pop();
    // Error: 谬误
    // while(second[1]--){//     ret.push(first[0])
    //     ret.push(second[0])
    //     first[1]--
    // }

    ret.push(first[0]);
    first[1]--;
    ret.push(second[0]);
    second[1]--;
    // 而后就要放回去了

    if (first[1]) {
      // 如果还有值，放回堆里再来
      heap.add(first);
    }
    if (second[1]) {
      // 如果还有值，放回堆里再来
      heap.add(second);
    }
  }
  if (heap.data[0]) {ret.push(heap.pop()[0]);
  }
  return ret;
};

class MaxHeap {constructor() {this.data = [];
    this.data[0] = 0;
  }

  down(index) {const lastIndex = this.data[0];
    while (index << 1 <= lastIndex) {
      let child = index << 1;
      if (
        child !== lastIndex &&
        this.data[child + 1][1] > this.data[child][1]
      ) {child++;}
      if (this.data[child][1] > this.data[index][1]) {[this.data[child], this.data[index]] = [this.data[index],
          this.data[child],
        ];
        index = child;
      } else {break;}
    }
  }

  upper() {let index = this.data[0];
    while (index >> 1 > 0) {
      let father = index >> 1;
      if (this.data[father][1] < this.data[index][1]) {[this.data[father], this.data[index]] = [this.data[index],
          this.data[father],
        ];
        index = father;
      } else {break;}
    }
  }

  add(item) {this.data.push(item);
    this.data[0]++;
    this.upper();}

  pop() {[this.data[1], this.data[this.data[0]]] = [this.data[this.data[0]],
      this.data[1],
    ];
    const item = this.data.pop();
    this.data[0]--;
    this.down(1);
    return item;
  }
}

console.log(rearrangeBarcodes([7, 7, 7, 8, 5, 7, 5, 5, 5, 8]));
退出移动版