当前位置: 首页 > news >正文

【leetcode】优先队列题目总结

 优先队列的底层是最大堆或最小堆

priority_queue<Type, Container, Functional>;

  • Type是要存放的数据类型
  • Container是实现底层堆的容器,必须是数组实现的容器,如vector、deque
  • Functional是比较方式/比较函数/优先级

priority_queue<Type>;

此时默认的容器是vector,默认的比较方式是大顶堆less<type>

常见的函数有:

  • top()
  • pop()
  • push()
  • emplace()
  • empty()
  • size()

 基本类型:

//小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//大顶堆
priority_queue <int,vector<int>,less<int> >q;
//默认大顶堆
priority_queue<int> a;//pair
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) 
{cout << a.top().first << ' ' << a.top().second << '\n';a.pop();
}
//输出结果为:
2 5
1 3
1 2

 自定义类型:

struct fruit
{string name;int price;
};// 1. 重载运算符  重载”<”
// 大顶堆
struct fruit
{string name;int price;friend bool operator < (fruit f1, fruit f2){return f1.peice < f2.price;}
};// 小顶堆
struct fruit
{string name;int price;friend bool operator < (fruit f1, fruit f2){return f1.peice > f2.price;  //此处是 >}
};// 此时优先队列的定义应该如下
priority_queue<fruit> q;// 2. 仿函数
// 大顶堆
struct myComparison
{bool operator () (fruit f1, fruit f2){return f1.price < f2.price;}
};struct myComparison
{bool operator () (fruit f1, fruit f2){return f1.price > f2.price;  //此处是 >}
};// 此时优先队列的定义应该如下
priority_queue<fruit, vector<fruit>, myComparison> q;

--------------------------------------------------------------------------------------------------------



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

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> pq;for (auto num : nums) {pq.push(num);if (pq.size() > k) {pq.pop();}}return pq.top();}
};

快排思想解法:

class Solution {
public:int partition(vector<int>& nums, int left, int right) {int randIndex = left + rand() % (right - left + 1);swap(nums[left], nums[randIndex]);int pivot = nums[left];while (left < right) {while (left < right && nums[right] >= pivot) {right--;}nums[left] = nums[right];while (left < right && nums[left] <= pivot) {left++;}nums[right] = nums[left];}nums[left] = pivot;return left;}int findKthLargest(vector<int>& nums, int k) {int left = 0, right = nums.size() - 1;int targetIndex = nums.size() - k;while (left <= right) {int mid = partition(nums, left, right);if (mid == targetIndex) {return nums[mid];} else if (mid < targetIndex) {left = mid + 1;} else {right = mid - 1;}}return INT_MIN;}
};

347. 前 K 个高频元素

class Solution {
public:struct compare {bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp;for (auto& num : nums) {mp[num]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;for (auto& item : mp) {pq.push(item);if (pq.size() > k) {pq.pop();}}vector<int> res;while (!pq.empty()) {res.push_back(pq.top().first);pq.pop();}return res;}
};

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

class KthLargest {
private:priority_queue<int, vector<int>, greater<int>> _pq;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for (auto& num : nums) {add(num);}}int add(int val) {_pq.push(val);if (_pq.size() > _k) {_pq.pop();}return _pq.top();}
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

295. 数据流的中位数

  • 大顶堆维护左半部分数据
  • 小顶堆维护右半部分数据
class MedianFinder {
public:priority_queue<int, vector<int>, less<int>> leftHeap;priority_queue<int, vector<int>, greater<int>> rightHeap;MedianFinder() {}void addNum(int num) {if (leftHeap.size() == rightHeap.size()) {rightHeap.push(num);leftHeap.push(rightHeap.top());rightHeap.pop();} else {leftHeap.push(num);rightHeap.push(leftHeap.top());leftHeap.pop();}}double findMedian() {return leftHeap.size() == rightHeap.size() ? (leftHeap.top() + rightHeap.top()) * 0.5 : leftHeap.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

23. 合并 K 个升序链表

优先队列

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:struct compare {bool operator() (const ListNode* lhs, const ListNode* rhs) {return lhs->val > rhs->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, compare> pq;for (auto& node : lists) {if (node != nullptr) {pq.push(node);}}ListNode* dummy = new ListNode(-1);ListNode* cur = dummy;while (!pq.empty()) {ListNode* node = pq.top();pq.pop();cur->next = node;cur = cur->next;if (node->next != nullptr) {pq.push(node->next);}}return dummy->next;}
};

二分+递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) {return list2;}if (list2 == nullptr) {return list1;}if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}return nullptr;}ListNode* mergeLists(vector<ListNode*>& lists, int left, int right) {if (left > right) {return nullptr;}if (left == right) {return lists[left];}int mid =  left + (right - left) / 2;return mergeTwoLists(mergeLists(lists, left, mid), mergeLists(lists, mid + 1, right));}ListNode* mergeKLists(vector<ListNode*>& lists) {return mergeLists(lists, 0, lists.size() - 1);}
};

相关文章:

【leetcode】优先队列题目总结

优先队列的底层是最大堆或最小堆 priority_queue<Type, Container, Functional>; Type是要存放的数据类型Container是实现底层堆的容器&#xff0c;必须是数组实现的容器&#xff0c;如vector、dequeFunctional是比较方式/比较函数/优先级 priority_queue<Type>…...

typescript 中的泛型

泛型&#xff1a;解决 类、接口、方法的复用性、以及对不特定数据类型的支持 传入的参数与返回参数类型一致 泛型函数 // T表示泛型&#xff0c;具体什么类型是调用这个方法的时候决定的 function getData<T>(value: T): T {return value } getData<number>(123) …...

计算方法实验2(补充):列主元消元法解线性方程组

C源代码 #include<bits/stdc.h> using namespace std;// 列主元消去法求解线性方程组 vector<long double> Column_Elimination(vector<vector<long double>> A, vector<long double> b);int main() {vector<vector<long double>> …...

Qt扫盲-Qt D-Bus概述

Qt D-Bus概述 一、概述二、总线三、相关概念1. 消息2. 服务名称3. 对象的路径4. 接口5. 备忘单 四、调试五、使用Qt D-Bus 适配器1. 在 D-Bus 适配器中声明槽函数1. 异步槽2. 只输入槽3. 输入输出槽4. 自动回复5. 延迟回复 一、概述 D-Bus是一种进程间通信(IPC)和远程过程调用…...

懒洋洋作业讲解

懒洋洋作业讲解 环境配置 1.软件下载&#xff1a;DCloud - HBuilder、HBuilderX、uni-app、uniapp、5、5plus、mui、wap2app、流应用、HTML5、小程序开发、跨平台App、多端框架 2.软件介绍 HBuilder是由DCloud&#xff08;数字天堂&#xff09;推出的一款面向HTML5的Web开发…...

vue3 + ts实现canvas绘制的waterfall

实际运行效果&#xff08;仅包含waterfall图表部分&#xff09; component.vue <template><div ref"heatmap" :style"{ height: props.containerHeight px }" /> </template><script setup> import ColorMap from "color…...

代码随想录算法训练营第四十四天

sad的一天&#xff0c;明天开始上班&#xff0c;而且娃还行&#xff0c;媳妇儿状态不稳定&#xff0c;太难了也&#xff01;&#xff01;&#xff01; 完全背包 #include<vector> #include<iostream> using namespace::std; int main(){int N;//种类int V;//空间ci…...

【3dmax笔记】027:配置修改器集、工具栏自定义与加载

文章目录 一、配置修改器集二、自定义工具栏三、加载工具栏 一、配置修改器集 可以把自己常用的修改命令放到右边框中的部分&#xff0c;便于自己的操作&#xff0c;省去了每次都要花半天时间找命令的尴尬。新建一个二维或者三维物体&#xff0c;点击修改面板&#xff0c;点击…...

Reactor模型详解

目录 1.概述 2.Single Reactor 3.muduo库的Multiple Reactors模型如下 1.概述 维基百科对Reactor模型的解释 The reactor design pattern is an event handling pattern for handling service requests delivered concurrently to a service handler by one or more inputs.…...

内存卡罢工,数据危机?别急,有救!

在日常生活和工作中&#xff0c;我们越来越依赖于各种电子设备来存储重要数据。其中&#xff0c;内存卡因其便携性和大容量而广受欢迎。然而&#xff0c;当内存卡突然损坏打不开时&#xff0c;我们该如何应对&#xff1f;本文将为您详细解析这一问题&#xff0c;并提供有效的解…...

python爬虫实战

import requests import json yesinput(输入页数&#xff1a;) yesint(yes)headers {"accept": "application/json, text/plain, */*","accept-language": "zh-CN,zh;q0.9","content-type": "application/json",…...

k8s 资源文件参数介绍

Kubernetes资源文件yaml参数介绍 yaml 介绍 yaml 是一个类似 XML、JSON 的标记性语言。它强调以数据为中心&#xff0c;并不是以标识语言为重点例如 SpringBoot 的配置文件 application.yml 也是一个 yaml 格式的文件 语法格式 通过缩进表示层级关系不能使用tab进行缩进&am…...

mac系统安装steam报错-解决办法

今天给虚拟机装了个苹果系统&#xff0c;然后想装个steam&#xff0c;从steam的官方下载安装steam_osx.dmg时&#xff0c;总是报“steam_osx已损坏&#xff0c;无法打开&#xff0c;请移动到废纸篓“。搜了一下找到了解决办法&#xff0c;这里记录一下。 双击steam_osx.dmg时&…...

这个簇状柱形图怎么添加百分比?

这个图表是excel默认的图表配色&#xff0c;有的人做出来都那个百分比&#xff0c;一起来做一个这样的图表。 1.插入图表 选中数据区域&#xff0c;点击 插入选项卡&#xff0c;在图表那一栏&#xff0c;点一下柱形图右侧那个倒三角&#xff0c;在弹邮对话框中&#xff0c;选…...

Tomact安装配置及使用(超详细)

文章目录 web相关知识概述web简介(了解)软件架构模式(掌握)BS&#xff1a;browser server 浏览器服务器CS&#xff1a;client server 客户端服务器 B/S和C/S通信模式特点(重要)web资源(理解)资源分类 URL请求路径(理解)作用介绍格式浏览器通过url访问服务器的过程 服务器(掌握)…...

web后端——netbeans ide +jsp+servlet开发学习总结

目录 jsp基础 netbeans开发工具问题HTTP Status 405 - HTTP method POST is not supported......netbeans 提示无法启动GlassFish Server 4.1.1:服务器未运行时, HTTP 或 HTTPS 监听程序端口已被占用404 问题netbeans中项目中有多个html文件,如何单独运行某个文件&#xff1f;n…...

使用request-try-notifyState流程实现UI控制与状态反馈的完整闭环

1. 前言 在Qt编程时&#xff0c;我们经常会在界面上添加一些按钮&#xff0c;当按钮被点击时&#xff0c;执行某段代码&#xff0c;例如显示一个对话框、关闭窗口&#xff0c;保存文件等等。 这种由UI控件触发某种信号&#xff0c;通过信号槽触发目的代码执行的场景非常多。这…...

屏蔽罩材质和厚度对屏蔽效能的影响

​ 一&#xff0e;屏蔽效能的影响因素 屏蔽效能的影响因素主要有两个方面&#xff1a;屏蔽材料的特性和厚度&#xff1b;如下图所示&#xff0c;电磁波经过不同媒介时&#xff0c;会在分界面形成反射&#xff0c;穿过界面的电磁波一部分被反射回去&#xff0c;这部分能量损失…...

Qt简单离线音乐播放器

有上传本地音乐文件&#xff0c;播放&#xff0c;暂停&#xff0c;拖拉进度条等功能的播放器。 mainwindow.cpp #include "mainwindow.h" #include "ui_mainwindow.h" #include <QMediaPlayer> #include <QFileDialog> #include <QTime&g…...

微信小程序常用的api

基础API&#xff1a; wx.request&#xff1a;用于发起网络请求&#xff0c;支持GET、POST等方式&#xff0c;是获取网络数据的主要手段。wx.showToast&#xff1a;显示消息提示框&#xff0c;通常用于向用户展示操作成功、失败或加载中等状态。wx.showModal&#xff1a;显示模态…...

iOS xib布局

1.多次启动发现启动图和截屏的图片不一致,设置launch storyboard 不能到顶部 https://blog.csdn.net/u011960171/article/details/104053696/ 2.multipiler是比例&#xff0c;需要控制顺序1.视图&#xff0c;2父视图&#xff0c;选择宽度比例&#xff0c;默认是1 3.Aspect R…...

UNI-APP_拨打电话权限如何去掉,访问文件权限关闭

uniapp上架过程中一直提示&#xff1a;允许“app名”拨打电话和管理通话吗&#xff1f; uniapp配置文件&#xff1a;manifest.json “permissionPhoneState” : {“request” : “none”//拨打电话权限关闭 }, “permissionExternalStorage” : {“request” : “none”//访…...

Git知识点汇总表格总结

Git应该是现在各个做开发公司使用最广泛的版本管理工具了&#xff0c;还有一些公司可能用的SVN&#xff0c;不过总体来说&#xff0c;Git绝对是主流&#xff0c;SVN是集中式版本管理&#xff0c;使用起来相对Git更简单&#xff0c;不过功能相对Git也略显简略&#xff0c;Git的优…...

漫谈:C语言 奇葩的指针定义规则

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 C语言的语法很麻拐。 初学者的…...

spring boot中一般如何使用线程池

在Spring Boot中&#xff0c;线程池作为并发编程的核心工具&#xff0c;对于提升应用程序性能、优化资源利用和保证系统稳定性具有重要作用。本文将详细阐述如何在Spring Boot中正确使用线程池&#xff0c;包括配置参数、实例化、任务提交、监控及常见问题处理等环节&#xff0…...

Shader 纹理动画和顶点动画

一、内置变量--时间 要实现动画&#xff0c;我们需要把时间添加到计算当中&#xff0c;让画面可以随着时间变化而变化。在Unity Shader提供了如下关于时间的内置变量以便于在shader中访问时间实现各种动态效果。 名称类型描述_Timefloat4t是自该场景加载开始所经过的时间&…...

使用macof发起MAC地址泛洪攻击

使用macof发起MAC地址泛洪攻击 MAC地址泛洪攻击原理&#xff1a; MAC地址泛洪攻击是一种针对交换机的攻击方式&#xff0c;目的是监听同一局域网中用户的通信数据。交换机的工作核心&#xff1a;端口- MAC地址映射表。这张表记录了交换机每个端口和与之相连的主机MAC地址之间…...

力扣:1979. 找出数组的最大公约数(Java)

目录 题目描述&#xff1a;输入&#xff1a;输出&#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;返回数组中最大数和最小数的 最大公约数 。 两个数的 最大公约数 是能够被两个数整除的最大正整数。 输入&#xff1a; nums [2,5,6…...

电瓶车充电桩:潜藏的暴利行业,简单入门到月入万元!

近几年来&#xff0c;电瓶车凭借其环保、经济特点已成为居民出行的必备工具之一。而促使电瓶车快速普及的原因之一即是电瓶车充电桩的普及。如果留心观察的话&#xff0c;相信大家都可以看出&#xff0c;国内大部分小区都已安装了充电桩设备&#xff0c;电瓶车充电桩已实现了大…...

mac监听 linux服务器性能可视化(Grafana+Promethus+Node_exporter)

Grafana和promethus(普罗米修斯)的安装和使用 监控系统的Prometheus类似于一个注册中心&#xff0c;我们可以只需要配置一个Prometheus,而在其他服务器&#xff0c;只需要安装node_exporter,它们的数据流转就是通过exporter采集数据信息&#xff0c;然后告诉prometheus它的位置…...