leetcode Heap/Queue

3066. 超过阈值的最少操作数 II

输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        res = 0
        h = nums[:]
        heapify(h)
        while h[0] < k:
            x = heappop(h)
            y = heappop(h)
            heappush(h, x + x + y)
            res += 1
        return res

• 首先想到排序才能获得最小值，但如果每次更新都排序或2分搜索，巨慢，所以直接使用heap priority Q
• 这里面有两个点要注意：
  • heappush 和 heappop
  • 以及，用"加法"替换了"乘法"

Heap Vs. Priority Queue

Heap 直接对底层进行操作，相当快和轻量

import heapq
h = [10, 5, 20]
heapq.heapify(h) #这就是如何将已有list转化为heap

Priority queue在工程项目里更多用到，主要原因还是多线程的安全
以下是等效的例子：

它们最终都会输出：
处理任务: 打电话 (优先级: 1)
处理任务: 写邮件 (优先级: 2)
处理任务: 开会 (优先级: 3)

import heapq

tasks = [(2, '写邮件'), (1, '打电话'), (3, '开会')]  # 优先级, 任务
heapq.heapify(tasks)

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f'处理任务: {task} (优先级: {priority})')

from queue import PriorityQueue

tasks = PriorityQueue()
tasks.put((2, '写邮件'))
tasks.put((1, '打电话'))
tasks.put((3, '开会'))

while not tasks.empty():
    priority, task = tasks.get()
    print(f'处理任务: {task} (优先级: {priority})')

原文地址：https://blog.csdn.net/u013302570/article/details/145156399

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！