力扣75——堆/优先队列

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

总结leetcode75中的堆/优先队列算法题解题思路。
上一篇:力扣75——图广度优先搜索

1 数组中的第K个最大元素

题目:

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

题解:
最大堆
建立最大堆。然后依次取出k-1个,每取一个就重新修复最大堆。最后堆顶元素即为所求值。

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

2 无限集中的最小数字

题目:

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类:

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
int popSmallest() 移除 并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不 存在于无限集中,则将一个 num 添加
到该无限集中。

题解:
用set类型的s记录被删除的变量。用minV记录最小值。
如果采用最小堆,可以将1~1000的数据存入最小堆或优先级队列,然后实现删除插入。

class SmallestInfiniteSet {
public:
    int minV = 1;
    set<int> s;
    SmallestInfiniteSet() {
    }

    int popSmallest() {
        int res = minV;
        s.insert(minV);
        while (s.count(++minV)) {}
        return res;
    }
    
    void addBack(int num) {
        if (s.count(num)) s.erase(num);
        minV = min(minV, num);
    }
};

3 最大子序列的分数

题目:

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,两者长度都是 n ,再给你一个正整数
k 。你必须从 nums1 中选一个长度为 k 的 子序列 对应的下标。

对于选择的下标 i0 ,i1 ,..., ik - 1 ,你的 分数 定义如下:

nums1 中下标对应元素求和,乘以 nums2 中下标对应元素的 最小值 。
用公示表示: 
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]) 。
请你返回 最大 可能的分数。

一个数组的 子序列 下标是集合 {0, 1, ..., n-1} 中删除若干元素得到的剩余集合,
也可以不删除任何元素。

题解:
最小堆
对于nums2中的任意一个数nums2[i],如果它是k个数的最小值,则另外的k-1个数都应该比它大。所以,先对nums2进行降序排序,然后从第k大的数开始枚举。每次从现有数据中去除nums1[j]最小的那个,然后加入当前枚举到的值nums1[i],计算得分。
做法:先对nums2进行降序排序,然后按顺序取nums1中的k个数,nums2[k-1]为nums2的k个数的最小值。遍历时:从k个nums1数中pop掉最小的那个,然后加入nums1[i],重新计算分数。
nums1的pop过程可以用最小堆(优先级队列)来实现。

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        // 根据nums2的值排序,拿到一个降序的索引
        vector<int> ids(nums2.size());
        iota(ids.begin(), ids.end(), 0);
        sort(ids.begin(), ids.end(), [&](const int& i, const int& j) { return nums2[i] > nums2[j]; });
        // 使用优先队列,最小值权重最高
        priority_queue<int, vector<int>, greater<int>> pq;

        long long res = 0, sumV = 0;
        for (int i = 0; i < k; ++i) {
            pq.emplace(nums1[ids[i]]);
            sumV += nums1[ids[i]];
        }
        res = sumV * nums2[ids[k - 1]];

        for (int i = k; i < ids.size(); ++i) {
            if (nums1[ids[i]] > pq.top()) {
                // 无论 res需不需要更新,最小值都需要更新
                sumV += nums1[ids[i]] - pq.top();
                res = max(res, sumV * nums2[ids[i]]);
                pq.pop();
                pq.emplace(nums1[ids[i]]);
            }
        }

        return res;
    }
};


4 雇佣 K 位工人的总代价

题目:

给你一个下标从 0 开始的整数数组 costs ,其中 costs[i] 是雇佣第 i 位工人的代价。
同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人:

总共进行 k 轮雇佣,且每一轮恰好雇佣一位工人。
在每一轮雇佣中,从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人,
如果有多位代价相同且最小的工人,选择下标更小的一位工人。
比方说,costs = [3,2,7,7,1,2] 且 candidates = 2 ,第一轮雇佣中,我们选择第 4 位工
人,因为他的代价最小 [3,2,7,7,1,2] 。
第二轮雇佣,我们选择第 1 位工人,因为他们的代价与第 4 位工人一样都是最小代价,而且下标
更小,[3,2,7,7,2] 。注意每一轮雇佣后,剩余工人的下标可能会发生变化。
如果剩余员工数目不足 candidates 人,那么下一轮雇佣他们中代价最小的一人,如果有多位代价
相同且最小的工人,选择下标更小的一位工人。
一位工人只能被选择一次。
返回雇佣恰好 k 位工人的总代价

题解:
优先级队列
2个优先级队列,最小值权重最高,分别存储前candidates个和后candidates个costs。
每次判断哪个队列的队头值更小,则雇佣对应的工人,然后弹出队列。

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        long long ans = 0;
        int left = 0, right = costs.size() - 1;
        priority_queue<int, vector<int>, greater<int>> prePq, purPq;

        while (k--) {
            while (prePq.size() < candidates && left <= right) {
                prePq.emplace(costs[left++]);
            }
            while (purPq.size() < candidates && left <= right) {
                purPq.emplace(costs[right--]);
            }
            int a = prePq.empty() ? INT_MAX : prePq.top();
            int b = purPq.empty() ? INT_MAX : purPq.top();
            if (a <= b) {
                ans += a;
                prePq.pop();
            } else {
                ans += b;
                purPq.pop();
            }
        }

        return ans;
    }
};

1-4 解题总结

特点:数据有优先级。最大、最小、第k大、第k小。
工具:自己建立最大堆或最小堆、使用优先级队列priority_queue。文章来源地址https://www.toymoban.com/news/detail-653407.html

到了这里,关于力扣75——堆/优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【力扣·每日一题】2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

    题目链接 给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。 返回 字典序最大的 repeatLimitedString 。 如果在字符串 a 和 b 不同的第一个位置,字符串 a 中

    2024年01月17日
    浏览(54)
  • 算法leetcode|75. 颜色分类(rust重拳出击)

    给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums , 原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0 、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。 n == nums.length

    2024年02月10日
    浏览(41)
  • LeetCode 0630.课程表 III:贪心 + 优先队列

    力扣题目链接:https://leetcode.cn/problems/course-schedule-iii/ 这里有 n 门不同的在线课程,按从 1 到 n  编号。给你一个数组 courses ,其中 courses[i] = [duration i , lastDay i ] 表示第 i 门课将会 持续 上 duration i 天课,并且必须在不晚于 lastDay i 的时候完成。 你的学期从第 1 天开始。且不能

    2024年02月09日
    浏览(37)
  • 【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数

    动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本 C++算法:滑动窗口总结 map 优先队列 中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。 例如: [2,3,4],中位数是 3 [2,3],中位数是 (2 + 3) / 2 =

    2024年02月03日
    浏览(42)
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ

    思路分析: 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。 使用 path 向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 使用 numvisited 向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 在递归过程中

    2024年03月13日
    浏览(51)
  • [leetcode 优先队列] 2512. 奖励最顶尖的 K 名学生 M

    给你两个字符串数组 positive_feedback 和 negative_feedback ,分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。 一开始,每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分,每个负面的词会给学生的分数 减 1 分。 给你 n 个学生的评语,用一个下标从

    2024年02月07日
    浏览(35)
  • (C语言版)力扣(LeetCode)栈和队列面试题

    给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 题目链接: 有效的括号 代码如下:

    2024年02月05日
    浏览(38)
  • LeetCode·每日一题·1851. 包含每个查询的最小区间·优先队列(小顶堆)

        离线查询:  输入的结果数组queries[]是无序的。如果我们按照输入的queries[]本身的顺序逐个查看,时间复杂度会比较高。 于是,我们将queries[]数组按照数值大小,由小到大逐个查询,这种方法称之为离线查询。 位运算:  离线查询的时候,queries[]可以按照数值大小逐个

    2024年02月16日
    浏览(49)
  • 剑指 Offer 59 - I. 滑动窗口的最大值 / LeetCode 239. 滑动窗口最大值(优先队列 / 单调队列)

    链接:剑指 Offer 59 - I. 滑动窗口的最大值;LeetCode 239. 滑动窗口最大值 难度:困难 下一篇:剑指 Offer 59 - II. 队列的最大值(单调队列) 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗

    2024年02月15日
    浏览(41)
  • 【数据结构与算法】03 队列(顺序队列--循环队列--优先级队列--链队列)

    队列( queue )是一种常见的数据结构,它遵循先进先出(FIFO)的原则。队列可以理解为一个具有两个端点的线性数据结构,其中一个端点称为\\\"队尾\\\"(rear),用于插入新元素,另一个端点称为\\\"队首\\\"(front),用于移除元素。新元素被插入到队尾,而最早插入的元素总是在队

    2024年02月08日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包