算法沉淀——优先级队列(堆)(leetcode真题剖析)

这篇具有很好参考价值的文章主要介绍了算法沉淀——优先级队列(堆)(leetcode真题剖析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法沉淀——优先级队列(堆)(leetcode真题剖析),算法沉淀,算法,leetcode,linux


优先队列(Priority Queue)是一种抽象数据类型,它类似于队列(Queue),但是每个元素都有一个关联的优先级。在优先队列中,元素按照优先级从高到低(或从低到高)排列,高优先级的元素先出队。这种数据结构可以用堆(Heap)来实现。

堆是一种二叉树结构,有两种主要类型:最大堆和最小堆。在最大堆中,每个节点的值都大于或等于其子节点的值;而在最小堆中,每个节点的值都小于或等于其子节点的值。对于优先队列来说,最大堆常常用于实现。

在堆中,根节点的元素具有最高(或最低)优先级,而且这一性质对于整个堆中的每个节点都成立。这确保了当我们从堆中移除元素时,总是移除具有最高(或最低)优先级的元素。

优先队列的常见操作包括:

  • 插入(Insertion):将元素插入队列中。
  • 删除最大(或最小)元素:移除并返回队列中具有最高(或最低)优先级的元素。

堆的实现可以通过数组或链表等数据结构。在使用数组实现堆时,父节点和子节点之间的关系可以通过数组的索引关系来表示。在C++中,可以使用 std::priority_queue 来实现优先队列,它默认使用最大堆,也可以通过传递自定义比较函数来实现最小堆。

01.最后一块石头的重量

题目链接:https://leetcode.cn/problems/last-stone-weight/

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 xy,且 x <= y。那么粉碎的可能结果如下:

  • 如果 x == y,那么两块石头都会被完全粉碎;
  • 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x

最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0

示例:

输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],
接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],
最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。 

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

思路

我们可以每次拿出最大的两个相比较,有差值就将差值保留,相等就都粉碎,这样我们很容易想到使用堆去计算,因为这符合堆的特性,我们可以使用各语言库中的堆容器来计算。

  1. 创建最大堆(Max Heap): 通过 priority_queue<int> 创建一个默认为最大堆的优先队列,将给定的石头数组中的元素加入最大堆中。
  2. 迭代处理: 使用一个循环迭代处理,直到堆中剩余的元素个数小于等于1。
  3. 从堆中取出两个最大的元素,执行碎石操作: 每次取出堆中的两个最大元素(即石头的重量最大的两块),执行碎石操作,计算碎石后的重量,将结果加回堆中。
  4. 返回结果: 当循环结束时,堆中剩余的元素即为最后一块石头的重量,或者堆为空,返回相应的结果。

代码文章来源地址https://www.toymoban.com/news/detail-835012.html

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> heap;
        for(int x:stones) heap.push(x);

        while(heap.size()>1){
            int a=heap.top(); heap.pop();
            int b=heap.top(); heap.pop();
            if(a>b) heap.push(a-b);
        }

        return heap.size()?heap.top():0;
    }
};

02.数据流中的第 K 大元素

题目链接:https://leetcode.cn/problems/kth-largest-element-in-a-stream/

设计一个找到数据流中第 k 大元素的类(class)。注意是排序后的第 k 大元素,不是第 k 个不同的元素。

请实现 KthLargest 类:

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val)val 插入数据流 nums 后,返回当前数据流中第 k 大的元素。

示例:

输入:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出:
[null, 4, 5, 5, 8, 8]

解释:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

提示:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104
  • 题目数据保证,在查找第 k 大元素时,数组中至少有 k 个元素

思路

这里是典型的topk问题,找的是第k个大的数,所以我们使用一个k大的小堆就能很好的解决这个问题。

在构造函数中,将初始的元素加入最小堆中,并维护堆的大小为 K,保证堆中只有前 K 大的元素。

当有新元素加入时,将新元素加入最小堆中,然后检查堆的大小是否超过 K,如果超过则弹出堆顶元素。最终返回当前堆顶元素,即为第 K 大的元素。这样,通过不断地将新元素加入最小堆,并保持堆的大小为 K,可以在 add 操作后始终保持堆中的元素为前 K 大的元素,而堆顶元素即为第 K 大的元素。

代码

class KthLargest {
    priority_queue<int,vector<int>,greater<int>> heap;
    int _k;
public:
    KthLargest(int k, vector<int>& nums) {
        _k=k;
        for(int& x:nums){
            heap.push(x);
            if(heap.size()>k) heap.pop();
        }
    }
    
    int add(int val) {
        heap.push(val);
        if(heap.size()>_k) heap.pop();
        return heap.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

03.前K个高频单词

题目链接:https://leetcode.cn/problems/top-k-frequent-words/

给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按字典顺序 排序。

示例 1:

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词,均为2次。
    注意,按字母顺序 "i" 在 "love" 之前。

示例 2:

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词,
    出现次数依次为 4, 3, 2 和 1 次。

注意:

  • 1 <= words.length <= 500
  • 1 <= words[i] <= 10
  • words[i] 由小写英文字母组成。
  • k 的取值范围是 [1, **不同** words[i] 的数量]

**进阶:**尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

思路

很显然这里这是还是topk问题,还是使用堆来解决问题,但是这里有两个比较条件,所以我们要注意比较函数的实现,主逻辑是找出前k个出现次数最多的,所以整体我们建小堆,还有一个附属条件,次数相同时,字典序小的排在前面,所以在相同次数时,我们相对于字符串建大堆,将字母小的排在前面。

  1. 哈希表统计频率: 使用 unordered_map 哈希表记录每个字符串出现的频率。
  2. 优先队列: 使用一个自定义的比较函数对象 cmp 作为优先队列的比较规则。按照频率从大到小排序,若频率相同则按照字符串字典序从小到大排序。遍历哈希表,将每个键值对(字符串及其频率)加入最小堆,并保持堆的大小为 K,当堆的大小超过 K 时,弹出堆顶元素。
  3. 结果处理: 从堆中依次取出前 K 高的字符串,存储到结果数组中。

最终,返回存储前 K 高字符串的结果数组 ret。这样通过哈希表统计频率,并使用优先队列来维护前 K 高的频率,实现了找出频率前 K 高的字符串。

代码

class Solution {
    struct cmp{
        bool operator()(const pair<string,int>& a,const pair<string,int>& b){
            if(a.second==b.second) return a.first<b.first;
            return a.second>b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        for(string& s:words) hash[s]++;

        priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> heap;

        for(const pair<string,int>& x:hash){
            heap.push(x);
            if(heap.size()>k) heap.pop();
        }

        vector<string> ret(k);
        for(int i=k-1;i>=0;--i){
            ret[i]=heap.top().first;
            heap.pop();
        }

        return ret;
    }
};

04.数据流的中位数

题目链接:https://leetcode.cn/problems/find-median-from-data-stream/

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

  • -105 <= num <= 105
  • 在调用 findMedian 之前,数据结构中至少有一个元素
  • 最多 5 * 104 次调用 addNumfindMedian

思路

这里我们最容易想到的暴力解法就是每次插入时排序,但是这种方法时间复杂度太高,其实这里我们可以使用一个大堆和一个小堆来维护所有数,各分一半数据,若两边长度相等,则返回两个堆顶相加除2的值,若不等,返回大堆堆顶即可。

在构造函数中初始化两个优先队列,left 用于存放较小的一半元素(最大堆),right 用于存放较大的一半元素(最小堆)。 在 addNum 方法中,根据元素的大小选择将其插入到左堆或右堆。插入后需要保持两个堆的大小差不超过 1,以确保中位数的计算。 在 findMedian 方法中,根据两个堆的大小关系返回中位数。通过这种方式,不断将数据插入到两个堆中,并保持它们的大小差不超过 1,就能够在 O(1) 时间内查找到当前数据流的中位数。

代码

class MedianFinder {
    priority_queue<int> left;
    priority_queue<int,vector<int>,greater<int>> right;
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if(left.size()==right.size()){
            if(left.empty()||num<=left.top()) left.push(num);
            else{
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else{
            if(num<=left.top()){
                left.push(num);
                right.push(left.top());
                left.pop();
            }else right.push(num);
        }
    }
    
    double findMedian() {
        if(left.size()==right.size()) return (left.top()+right.top())/2.0;
        return left.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

到了这里,关于算法沉淀——优先级队列(堆)(leetcode真题剖析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Linux_进程的优先级&&环境变量&&上下文切换&&优先级队列

    什么是优先级? 指定一个进程获取某种资源的先后顺序 本质是进程获取cpu资源的优先顺序 为什么要有优先级 进程访问的资源(CPU)是有限的 操作系统关于调度和优先级的原则:分时操作系统,基本的公平,如果进程因为长时间不被调整,就造成了饥饿问题 Linux的优先级特

    2024年04月09日
    浏览(58)
  • 优先级队列

    目录  前言: 1、PriorityQueue的特性 .2 PriorityQueue常用接口介绍 Ⅰ、PriorityQueue常见的构造方法  Ⅱ、常用的方法 Ⅲ、PriorityQueue的扩容方式:  3、应用 普通的队列是一种 先进先出 的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元

    2024年02月02日
    浏览(65)
  • 优先级队列【C++】

    优先队列(priority_queue)也是队列的一种,priority_queue的接口是和queue的接口是相同的。所以两者的使用语法也是相同的。我们直接看优先队列(priority——queue)的底层实现原理。 默认情况下priority_queue是大堆。 priority_queue的底层实际上就是堆,模拟实现priority_queue之前,需要

    2024年02月10日
    浏览(44)
  • 【JAVA】优先级队列(堆)

    羡慕别人就让自己变得更好! 优先级队列(堆)可用于topK问题 有大小根堆 注意堆的模拟实现 坚持真的很难但是真的很酷! 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。 此时,数据结

    2024年02月15日
    浏览(51)
  • Java优先级队列-堆

    大家好,我是晓星航。今天为大家带来的是 Java优先级队列(堆) 的讲解!😀 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。 这种方式的主要用法就是堆的表示。 已知双亲(parent)的下

    2023年04月16日
    浏览(41)
  • 「数据结构」优先级队列

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! 优先级队列底层是用堆实现的 ,关于堆的实现,之前的文章已经详细介绍过了,文章链接:二叉树1:堆的实现 方法 功能 PriorityQueue() 创建一个空的优先级队列,默认容量是11 PriorityQueue(int i

    2024年02月20日
    浏览(44)
  • rabbitmq的优先级队列

    在我们系统中有一个 订单催付 的场景,我们的客户在天猫下的订单 , 淘宝会及时将订单推送给我们,如果在用户设定的时间内未付款那么就会给用户推送一条短信提醒,很简单的一个功能对吧,但是,tianmao商家对我们来说,肯定是要分大客户和小客户的对吧,比如像苹果,

    2024年02月11日
    浏览(47)
  • 【Java】PriorityQueue--优先级队列

    目录  一、优先级队列  (1)概念 二、优先级队列的模拟实现 (1)堆的概念  (2)堆的存储方式   (3)堆的创建 堆向下调整 (4)堆的插入与删除 堆的插入  堆的删除 三、常用接口介绍 1、PriorityQueue的特性 2、PriorityQueue常用接口介绍   (1)优先级队列的构造 (2)插入

    2024年02月11日
    浏览(47)
  • 数据结构-优先级队列(堆)

    文章目录 目录 文章目录 前言 一 . 堆 二 . 堆的创建(以大根堆为例) 堆的向下调整(重难点)  堆的创建  堆的删除 向上调整 堆的插入 三 . 优先级队列 总结 大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列 堆(Heap)是一种基于完全二叉树的数据结构,具有

    2024年02月08日
    浏览(50)
  • java 堆(优先级队列)详解

    如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki = K2i+1 且 Ki= K2i+2 (Ki = K2i+1 且 Ki = K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包