leetcode - 堆题目总结

[Caaalabash]

堆

堆是优先队列的实现，可以用于动态选取一个集合中的最值元素。

下面是JS版本的堆实现（仅用于做题）

class Heap {
  constructor(data = [], less) {
    this.data = data
    this.less = less || ((a, b) => a < b)
    // 对初始数组进行堆化操作：从最后一个父节点开始，依次下沉 
    if (this.length) {
      for (let p = (this.length - 2) >> 1; p >= 0; p--) {
        this._down(p)
      }
    }
  }
  get length() {
    return this.data.length
  }
  peak() {
    return this.data[0]
  }
  push(val) {
    this.data.push(val)
    this._up(this.length - 1)
  }
  pop() {
    if (!this.length) {
      return
    }
    this._swap(0, this.length - 1)
    const popItem = this.data.pop()
    this._down(0)
    return popItem
  }
  // 删除指定值的操作，通常堆是不含这个操作的，针对特定题目，添加上这个操作
  remove(val) {
    let index = -1
    for (let i = 0; i < this.length; i++) {
      if (this.data[i] === val) {
        index = i
        break
      }
    }
    if (index === -1) return false
    this._swap(index, this.length - 1)
    this.data.pop()
    this._up(index)
    this._down(index)
    return true
  }
  _swap(i, j) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }
  // 递归上浮
  _up(i) {
    if (i <= 0) return
    const pIndex = (i - 1) >> 1
    if (this.less(this.data[i], this.data[pIndex])) {
      this._swap(i, pIndex)
      this._up(pIndex)
    }
  }
  // 递归下沉
  _down(i) {
    let leftIndex = i * 2 + 1
    if (leftIndex >= this.length) {
      return
    }
    if (leftIndex + 1 < this.length && this.less(this.data[leftIndex+1], this.data[leftIndex])) {
      leftIndex++
    }
    if (this.less(this.data[leftIndex], this.data[i])) {
      this._swap(leftIndex, i)
      this._down(leftIndex)
    }
  }
}

题目总结

• 23: 链表 + 堆的基本操作
• 355：设计题目，核心部分等价于23题，合并K个有序链表
• 378：堆的基本操作，等价于23题
• 215: 堆的基本操作
• 347：堆的基本操作
• 373：堆的基本操作
• 1054：堆的基本操作，穿插数组比较亮眼
• 295：经典双堆
• 857：深入了解资本家
• 407：3D 接雨水

leetcode 23 - 困难

解题思路：

链表 + 普通的堆操作，没有什么特别值得说的地方

实现：

function mergeKLists(lists) {
  // 需要过滤空链表，然后构建一个最小堆
  const heap = new Heap(lists.filter(i => !!i), (a, b) => a.val < b.val)
  const dummy = { next: null }
  let cur = dummy

  while (heap.length) {
    const item = heap.pop()
    cur.next = { val: item.val, next: null }
    if (item.next) {
      heap.push(item.next)
    }
    cur = cur.next
  }

  return dummy.next
}

leetcode 355 - 中等

解题思路：

设计题目，发挥空间挺大的，关键在于：getNewsFeed等价于按时间排序相关人员的博文列表，然后取10条，等价于23题

实现：

class Twitter {
  constructor() {
    // 代表时间
    this.timeSid = 0
    // 关注map，O(1)时间关注/取关即可
    this.followMap = {}
    // 推文map
    this.articlesMap = {}
  }
  postTweet(userId, tweetId) {
    if (!(userId in this.articlesMap)) {
      this.articlesMap[userId] = []
    }
    this.articlesMap[userId] = [ { tweetId, timeSid: this.timeSid++ }, ...this.articlesMap[userId] ]
  }
  getNewsFeed(userId) {
    const list = Object.keys(this.followMap).concat(`${userId}-${userId}`)
    const followerArticleList = []
    for (let i = 0; i < list.length; i++) {
      if (list[i].startsWith(`${userId}-`)) {
        const [,id] = list[i].split('-')
        if (id in this.articlesMap && this.articlesMap[id].length) {
          followerArticleList.push(this.articlesMap[id])
        }
      }
    }
    // 问题转换为合并k个有序链表，最大堆
    const heap = new Heap(followerArticleList, (a, b) => {
      return a[0].timeSid > b[0].timeSid
    })
    const result = []

    while (result.length < 10 && heap.length) {
      const peak = heap.pop()
      const rest = peak.slice(1)
      if (rest.length) {
        heap.push(rest)
      }
      result.push(peak[0].tweetId)
    }

    return result
  }
  follow(followerId, followeeId) {
    const key = `${followerId}-${followeeId}`
    if (key in this.followMap) return
    this.followMap[key] = 1
  }
  unfollow(followerId, followeeId) {
    const key = `${followerId}-${followeeId}`
    if (!(key in this.followMap)) return
    delete this.followMap[key]
  }
}

leetcode 378 - 中等

解题思路：

同23题

实现：

function kthSmallest(matrix, k) {
  // 小顶堆
  const heap = new Heap([], (a, b) => {
    return a[0] < b[0]
  })
  for (let i = 0; i < matrix.length; i++) {
    heap.push(matrix[i])
  }
  for (let i = 0; i < k - 1; i++) {
    const row = heap.pop()
    if (row.length > 1) {
      heap.push(row.slice(1))
    }
  }
  return heap.peak()[0]
}

leetcode 215 - 中等

解题思路：

数组中的第K大的元素 ==> 维护一个大顶堆，pop掉前n-1个，剩下那个就是最大值

实现：

function findKthLargest(nums, k) {
  // 建立最大堆
  const heap = new Heap(nums, (a, b) => a > b)
  // pop 掉 k-1 个最大值
  for (let i = 0; i < k - 1; i++) {
    heap.pop()
  }
  // 当前最大值即是第k个最大元素
  return heap.peak()
}

leetcode 347 - 中等

解题思路：

建立频次哈希表，然后建立最大堆，然后pop k个

实现：

function topKFrequent(nums, k) {
  const counter = nums.reduce((map, num) => {
    if (!(num in map)) {
      map[num] = 1
    } else {
      map[num]++
    }
    return map
  }, {})
  const arr = Object.entries(counter).map(set => ({ value: +set[0], priority: set[1] }))
  const heap = new Heap(arr, (a, b) => a.priority > b.priority)

  const result = []
  for (let i = 0; i < k; i++) {
    result.push(heap.pop().value)
  }
  return result
}

leetcode 373 - 中等

解题思路：

堆的基本操作，没有什么值得说的

实现：

function kSmallestPairs(nums1, nums2, k) {
  const heap = new Heap([], (a, b) => {
    return a[0] + a[1] < b[0] + b[1]
  })
  for (const num1 of nums1) {
    for (const num2 of nums2) {
      heap.push([num1, num2])
    }
  }
  const result = []
  for (let i = 0; i < k; i++) {
    result.push(heap.pop())
  }
  return result.filter(Boolean)
}

leetcode 1054 - 中等

解题思路：

统计词频 -> 构建最大堆 -> 依次穿插

实现：

function rearrangeBarcodes(barcodes) {
  // 词频统计
  const counter = {}
  for (let i = 0; i < barcodes.length; i++) {
    if (barcodes[i] in counter) {
      counter[barcodes[i]]++
    } else {
      counter[barcodes[i]] = 1
    }
  }
  // 根据词频构建最大堆
  const heap = new Heap(Object.entries(counter), (a, b) => {
    return a[1] > b[1]
  })
  const result = new Array(barcodes.length)
  let i = 0

  while (heap.length) {
    let [value, frequency] = heap.pop()
    while (frequency > 0) {
      result[i] = value
      i += 2
      if (i >= barcodes.length) i = 1
      frequency--
    }
  }

  return result
}

leetcode 295 - 困难

解题思路：

维护两个堆，最大堆存储输入数字中较小的一半，最小堆存储输入数字中较大的一半，保持两个堆近似平衡

实现：

// 数据流中的中位数
class MedianFinder {
  constructor() {
    // 维护两个堆
    // 最大堆 存储输入数字中较小的一半，其长度最多只能比最小堆多1，这样便于返回中位数
    // 最小堆 存储输入数字中较大的一半
    this.minHeap = new Heap([], (a, b) => a < b)
    this.maxHeap = new Heap([], (a, b) => a > b)
  }
  addNum(num) {
    if (!this.maxHeap.length || num < this.maxHeap.peak()) {
      this.maxHeap.push(num)
    } else {
      this.minHeap.push(num)
    }
    this.makeBalance()
  }
  makeBalance() {
    if (this.maxHeap.length - this.minHeap.length > 1) {
      this.minHeap.push(this.maxHeap.pop())
    }
    if (this.minHeap.length > this.maxHeap.length) {
      this.maxHeap.push(this.minHeap.pop())
    }
  }
  findMedian() {
    if (this.maxHeap.length === this.minHeap.length) {
      return (this.maxHeap.peak() + this.minHeap.peak()) / 2
    }
    return this.maxHeap.peak()
  }
}

leetcode 857 - 困难

解决思路：

题目中的关键是："对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资"

那么通过wage[i] / quality[i]获得每个工人的"时薪"，按升序排列，排在前面的人意味着对资本家来说更便宜。

排序后的第 i 名工人可以在它之前任选 K - 1 名工人，此时，总支出为：

result = Math.min(result, (wage[i] / quality[i]) * (quality[c1], .... quality[c{k-1}] + quality[i]))

实现：

function mincostToHireWorkers(quality, wage, k) {
  // 计算"时薪"并升序排列，排在前面的意味着便宜
  // 排序后的第 i 名工人可以在它之前任选 K - 1 名工人
  // 工资总和为: ratio * sum(quality[c1] + quality[c2] + ... + quality[c{k-1}] + quality[i])
  const employeeInfo = quality.map((q, index) => ({
    q,
    w: wage[index],
    ratio: wage[index] / q,
  })).sort((a, b) => a.ratio < b.ratio ? -1 : 1)
  // 使用大根堆来维护k个最小值，使得sumQ尽可能小
  const heap = new Heap([], (a, b) => a > b)
  let result = Number.MAX_VALUE
  let sumQ = 0
  
  for (let employee of employeeInfo) {
    heap.push(employee.q)
    sumQ += employee.q
    if (heap.length > k) {
      sumQ -= heap.pop()
    }
    if (heap.length === k) {
      result = Math.min(result, employee.ratio * sumQ)
    }
  }
  
  return result
}

leetcode 407 - 困难

解题思路：

• 先排除不可能接水的情况，长度或者宽度不足3
• 维持一个二维数组visited记录哪些已经被遍历
• 维持一个优先级队列（按照高度从小到大排列）
• 先把周围一圈插入到队列里（这些无法放水）
• 基于广度优先方式，遍历优先级队列直到为空

实现：

// 从最外层的一圈开始，判断每个元素能不能向内拓展
function trapRainWater(heightMap) {
  // 排除不可能接到水的情况，长度/宽度不足3
  let row = heightMap.length
  if (row < 3) {
    return 0
  }
  let col = heightMap[0].length
  if (col < 3) {
    return 0
  }
  // 创建一个二维数组，代表是否已经被遍历过
  const visit = Array.from({ length: row }, () =>
    Array.from({ length: col }, () => false)
  )
  // 创建一个小顶堆，并将周围的一圈放进堆中
  const heap = new Heap([], (a, b) => a.val < b.val)
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (j === 0 || i === 0 || i === row - 1 || j === col - 1) {
        heap.push({
          r: i,
          c: j,
          val: heightMap[i][j]
        })
        visit[i][j] = true
      }
    }
  }
  const dir = [-1, 0, 1, 0, -1]
  let result = 0
  while (heap.length) {
    const { r, c, val } = heap.pop()
    // 遍历四个方向
    for (let i = 0; i < dir.length - 1; i++) {
      const offsetR = r - dir[i]
      const offsetC = c - dir[i+1]
      if (offsetR >= 0 && offsetR < row && offsetC >= 0 && offsetC < col && !visit[offsetR][offsetC]) {
        if (heightMap[offsetR][offsetC] < val) {
          result += val - heightMap[offsetR][offsetC]
        }
        visit[offsetR][offsetC] = true
        heap.push({
          r: offsetR,
          c: offsetC,
          val: Math.max(heightMap[offsetR][offsetC], val)
        })
      }
    }
  }
  return result
}