LeetCode冲刺：Day42

发布于 2022-12-19  1068 次阅读

堆

备考408时学习过堆这种数据结构，这次简单复习一下。

首先，可以将堆看作一个完全二叉树，所以一般用一维数组来存储，便于访问。

对于大根堆，总有当前结点值大于左右子结点值，小根堆相反。建堆的时间复杂度在 O(n) ，向堆中插入元素的时间复杂度在 O(logn) 。因此，堆特别适合用于需要频繁获取最小元素、插入新元素的场景。

在Python中，可以使用 heapq 模块来操作堆，具体见手册 。

最基本的，可以使用 heapify() 函数，将列表原地转换为堆，使用 heappop() 弹出最小元素；使用 heappush() 插入新元素；亦或者当需要先弹出最小元素，再插入新元素时，使用 heapreplace() （顺序相反时使用 heappushpop() ），则效率更佳。如果只需要获取而不需要弹出最小元素，可以直接使用下标0来访问。

1. K 次增加后的最大乘积

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

一个不难发现的事实，只有每次将最小值增加1，才能达成变更后乘积最大的结果。因此我们需要反复将数组中最小值加一。这可以通过以下步骤实现：

  1. 获取并弹出最小元素
  2. 将最小元素+1的值插入

所以可以用堆的 heapreplace() 函数很方便地实现。

代码

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        MOD = 1000000007
        heapify(nums)
        while k > 0:
            heapreplace(nums, nums[0] + 1)
            k -= 1
        ans = 1
        for num in nums:
            ans = (ans * num) % MOD
        return ans

2. 剑指 Offer 40. 最小的k个数

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

可以直接排序完成，也可以用堆。

代码

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        heapify(arr)
        return nsmallest(k, arr)

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

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

建堆，然后直接返回所求值即可。

代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapify(nums)
        return nlargest(k, nums)[k - 1]

4. 合并K个升序链表

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

服气，Debug十分钟。明明是 ListNode 类重复定义，不报重复定义的错，一直报什么类型错误，无语。

也可以先把所有元素加入数组再 heapify()

代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ans = []
        n = len(lists)
        for i in range(n):
            cur = lists[i]
            while cur != None:
                heappush(ans, cur.val)
                cur = cur.next
        dummy = ListNode()
        cur = dummy
        while ans != []:
            cur.next = ListNode(heappop(ans))
            cur = cur.next
        return dummy.next

5. 滑动窗口最大值

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

双端队列

先看一个双端队列的解法。

首先认识到，在一个窗口中，最大元素左侧的元素都是没用的，因为他们一定会在最大元素滑出之前滑出，所以我们在新元素入队前，先将其左侧的比它小的元素滑出，这样一来，窗口中的最大元素，一定是当前窗口最左侧的元素。为了判断窗口大小，我们在队中存储下标而非元素。这样，从最左侧下标就能判断出当前窗口大小（或者说是否应当滑出当前最大元素，即最左侧元素）。

大根堆

Python中没有真正的大根堆，所以我们用元素取负值的方式来间接构造大根堆。

具体思路上，其实跟双端队列差不多。也是利用当前最大元素的下标来判断是否应当将其滑出。实际上是把所有元素都存在了堆里，然后每次看当前最大元素下标是否在窗口内，在的话就加入ans，不在的话就将其弹出。

代码

双端队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n == 1: return nums
        ans = []
        queue = []

        for i in range(n):
            if queue and queue[0] == i - k: queue.pop(0)
            while queue and nums[queue[-1]] < nums[i]: queue.pop()
            queue.append(i)
            if i >= k - 1: ans.append(nums[queue[0]])

        return ans

大根堆

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 大根堆
        hp, ans = [], []
        for i, num in enumerate(nums):
            while hp and hp[0][1] <= i - k: heappop(hp)
            heappush(hp, [-num, i])
            if i >= k - 1: ans.append(-hp[0][0])
        return ans

从代码也不难看出，Python的数组枚举，返回的元组，第一项是下标，第二项是元素。以及，堆中元素可以是列表（元组亦可），将按首元素为 Key 进行堆操作。

6. 丑数 II

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

做这题要意识到丑数的生成过程。从元素仅有1的集合开始，每次从中取出最小元素，分别乘以2、3、5再放回，且不能重复放入相同元素，这是丑数的生成过程。如果没想出这个过程，也就做不出这题。

代码

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        hp = [1]
        cnt = 0
        factors = [2, 3, 5]
        records = set()
        while True:
            cur = heappop(hp)
            cnt += 1
            if cnt == n: return cur
            for factor in factors:
                if (cur * factor) not in records:
                    heappush(hp, cur * factor)
                    records.add(cur * factor)

7. 前 K 个高频元素

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

  1. 用字典统计元素频率
  2. 用二维数组存储频率和对应元素
  3. 将二维数组转换为堆
  4. 获取频率最高的k个元素

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = defaultdict(int)
        for num in nums: dic[num] += 1
        nums = dic.keys()
        freq = []
        for num in nums: freq.append([dic[num], num])
        heapify(freq)
        res = nlargest(k, freq)
        ans = []
        for elem in res: ans.append(elem[1])
        return ans

8. 设计推特

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

稍微有点绕。核心部分在于，需要一个全局时间戳（因为这里只有一个推特实例，所以不用写成类变量），每个用户有一个堆，按时间戳排序存储推文，每个用户一个集合，存储其关注的用户。

在获取推送时，将用户自身以及所关注的用户的前十条最新推文（时间戳最大）推文放到一个堆里，再取出最大的十个，其ID即为所求。

设计类题目要打草稿，列出每个功能的实现逻辑和变量需求。

代码

from collections import defaultdict
from heapq import heappop, heappush, nlargest
from typing import List, Set

class Twitter:
    __time: int
    # 每个用户一个堆保存前十条推文
    __tweets: List[List[int]]
    # 每个用户一个集合保存关注用户
    __followed: List[Set[int]]
    def __init__(self):
        self.__time = 0
        self.__tweets = [[] for i in range(501)]
        self.__followed = [set() for i in range(501)]

    def postTweet(self, userId: int, tweetId: int) -> None:
        tweet = [self.__time, tweetId]
        self.__time += 1
        heappush(self.__tweets[userId], tweet)
        while len(self.__tweets[userId]) > 10: heappop(self.__tweets[userId])

    def getNewsFeed(self, userId: int) -> List[int]:
        tweets = nlargest(10, self.__tweets[userId])
        for followee in self.__followed[userId]:
            curTweets = nlargest(10, self.__tweets[followee])
            for tweet in curTweets: heappush(tweets, tweet)
        newTweets = nlargest(10, tweets)
        ans = [newTweets[i][1] for i in range(len(newTweets))]
        return ans

    def follow(self, followerId: int, followeeId: int) -> None:
        self.__followed[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.__followed[followerId].discard(followeeId)