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

【算法刷题指南】优先级队列

在这里插入图片描述

🌈个人主页: 南桥几晴秋
🌈C++专栏: 南桥谈C++
🌈C语言专栏: C语言学习系列
🌈Linux学习专栏: 南桥谈Linux
🌈数据结构学习专栏: 数据结构杂谈
🌈数据库学习专栏: 南桥谈MySQL
🌈Qt学习专栏: 南桥谈Qt
🌈菜鸡代码练习: 练习随想记录
🌈git学习: 南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
本科在读菜鸡一枚,指出问题及时改正

文章目录

  • 1046.最后一块石头的重量
  • 703.数据流中的第k大元素
  • 692.前K个高频单词
  • 295. 数据流的中位数


1046.最后一块石头的重量

1046.最后一块石头的重量

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto 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;}
};

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

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

class KthLargest {priority_queue<int,vector<int>,greater<int>> heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k=k;for(auto 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);*/

692.前K个高频单词

692.前K个高频单词

class Solution {typedef pair<string,int> PSI;struct cmp{bool operator()(const PSI& a,const PSI& 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(auto &s:words) hash[s]++;priority_queue<PSI,vector<PSI>,cmp> heap;for(auto &pis:hash){heap.push(pis);if(heap.size()>k) heap.pop();}vector<string> ans(k);for(int i=k-1;i>=0;i--){ans[i]=heap.top().first;heap.pop();}return ans;}
};

295. 数据流的中位数

295. 数据流的中位数

二分查找+插入排序

#include<algorithm>
#include<vector>
class MedianFinder {
public:MedianFinder() {}vector<int> newarr;void addNum(int num) {auto it=lower_bound(newarr.begin(),newarr.end(),num);newarr.insert(it,num);}double findMedian() {int n=newarr.size();if(n%2==1) return newarr[n/2];else return  (newarr[n / 2 - 1] + newarr[n / 2]) / 2.0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

优先队列

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;else 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();*/

在这里插入图片描述

相关文章:

【算法刷题指南】优先级队列

&#x1f308;个人主页&#xff1a; 南桥几晴秋 &#x1f308;C专栏&#xff1a; 南桥谈C &#x1f308;C语言专栏&#xff1a; C语言学习系列 &#x1f308;Linux学习专栏&#xff1a; 南桥谈Linux &#x1f308;数据结构学习专栏&#xff1a; 数据结构杂谈 &#x1f308;数据…...

使用pymupdf提取PDF文档中的文字和其颜色

最近我在捣鼓一个PDF文件&#xff0c;想把它里面的文字和文字颜色给提取出来。后来发现有个叫pymupdf的库能搞定这事儿。操作起来挺简单的&#xff0c;pymupdf的示例文档里就有现成的代码可以参考。 how-to-extract-text-with-color 我本地的测试代码如下&#xff1a; impor…...

贪心算法题

0简介 0.1什么是贪心算法 贪心算法是用贪婪(鼠目寸光)的角度&#xff0c;找到解决问题的最优解 贪心策略&#xff1a;(从局部最优 --> 整体最优) 1把解决问题的过程分为若干步&#xff1b; 2解决每一个问题时&#xff0c;都选择当前“看上去”最优的解法&#xff1b; 3“…...

Python 3 教程第33篇(MySQL - mysql-connector 驱动)

Python MySQL - mysql-connector 驱动 MySQL 是最流行的关系型数据库管理系统&#xff0c;如果你不熟悉 MySQL&#xff0c;可以阅读我们的 MySQL 教程。 本章节我们为大家介绍使用 mysql-connector 来连接使用 MySQL&#xff0c; mysql-connector 是 MySQL 官方提供的驱动器。…...

23种设计模式之外观模式

目录 1. 简介2. 代码2.1 SelectFoodService (选择食品)2.2 PayService (支付服务)2.3 TakeService (制作服务)2.4 OrderService (下单服务)2.5 Food (食品)2.6 TackingSystem &#xff08;外观类&#xff09;2.7 Test &#xff08;测试类&#xff09; 3. 优缺点3. 总结 1. 简介…...

GateWay使用手册

好的&#xff0c;下面是优化后的版本。为了提高可读性和规范性&#xff0c;我对内容进行了结构化、简化了部分代码&#xff0c;同时增加了注释说明&#xff0c;便于理解。 1. 引入依赖 在 pom.xml 中添加以下依赖&#xff1a; <dependencies><!-- Spring Cloud Gate…...

MySQL1.0

1.数据库的三大范式 范式是为了使数据库设计更加合理&#xff0c;规范&#xff0c;减少数据冗余和数据不一致等问题指定的一系列规则。 第一范式&#xff1a;第一范式要求数据表中的每一列都是不可分割的原子数据项。例如&#xff1a;有一个学生信息表&#xff0c;包含 “学生…...

IDEA使用HotSwapHelper进行热部署

目录 前言JDK1.8特殊准备DECVM安装插件安装与配置参考文档相关下载 前言 碰到了一个项目&#xff0c;用jrebel启动项目时一直报错&#xff0c;不用jrebel时又没问题&#xff0c;找不到原因&#xff0c;又不想放弃热部署功能 因此思考能否通过其他方式进行热部署&#xff0c;找…...

简单web项目自定义部署Dockerfile

本意就是弄清楚如何做web自定义项目的镜像。 基础镜像是java:8u261-jdk&#xff0c;其中java路径为/opt/java webdemo1.0.0.1-SNAPSHOT.jar文件里面已经包含了lib文件。 可以设置PATH也可以不设置&#xff0c;但是建议设置JAVA_HOME FROM swr.cn-north-4.myhuaweicloud.com…...

基础Web安全|SQL注入

基础Web安全 URI Uniform Resource Identifier&#xff0c;统一资源标识符&#xff0c;用来唯一的标识一个资源。 URL Uniform Resource Locator&#xff0c;统一资源定位器&#xff0c;一种具体的URI&#xff0c;可以标识一个资源&#xff0c;并且指明了如何定位这个资源…...

SpringBoot -拦截器Interceptor、过滤器 Filter 及设置

Spring Boot拦截器&#xff08;Interceptor&#xff09;的概念 - 在Spring Boot中&#xff0c;拦截器是一种AOP的实现方式。它主要用于<font style"color:#DF2A3F;">拦截请求</font>&#xff0c;在请求处理之前和之后执行特定的代码逻辑。与过滤器不同的…...

C++小问题

怎么分辨const修饰的是谁 是限定谁不能被改变的&#xff1f; 在C中&#xff0c;const关键字的用途和位置非常关键&#xff0c;它决定了谁不能被修改。const可以修饰变量、指针、引用等不同的对象&#xff0c;并且具体的作用取决于const的修饰位置。理解const的规则能够帮助我们…...

avcodec_alloc_context3,avcodec_open2,avcodec_free_context,avcodec_close

avcodec_alloc_context3 是创建编解码器上下文&#xff0c;需要使用 avcodec_free_context释放 需要使用avcodec_free_context 释放 /** * Allocate an AVCodecContext and set its fields to default values. The * resulting struct should be freed with avcodec_free_co…...

强化学习的几个主要方法(策略梯度、PPO、REINFORCE实现等)(下)

由于平台字数限制&#xff0c;上文&#xff1a;https://blog.csdn.net/ooblack/article/details/144198538 4. PPO算法 近端策略优化&#xff08;proximal policy optimization&#xff0c;PPO&#xff09;算法是OpenAI的默认强化学习算法&#xff0c;在RLHF中也用到了这个算…...

计算机网络:IP协议详细讲解

目录 前言 一、IP网段划分 二、IP报头 三、解决IP地址不足-->NAT技术 前言 在之前&#xff0c;我们学习了传输层中的TCP和UDP&#xff0c;重点是TCP协议&#xff0c;他帮我们解决具体到主机的哪个应用&#xff08;端口&#xff09;、传输的可靠&#xff08;序列号、校验和…...

2024信创数据库TOP30之华为Gauss DB

近日&#xff0c;由DBC联合CIW/CIS共同发布的“2024信创数据库TOP30”榜单正式揭晓&#xff0c;汇聚了国内顶尖的数据库企业及其产品&#xff0c;成为展示中国信创领域技术实力与发展潜力的重要平台。在这份榜单中&#xff0c;华为的GaussDB凭借其卓越的技术实力、广泛的行业应…...

在线家具商城基于 SpringBoot:设计模式与实现方法探究

第3章 系统分析 用户的需求以及与本系统相似的在市场上存在的其它系统可以作为系统分析中参考的资料&#xff0c;分析人员可以根据这些信息确定出本系统具备的功能&#xff0c;分析出本系统具备的性能等内容。 3.1可行性分析 尽管系统是根据用户的要求进行制作&#xff0c;但是…...

九、Spring Boot集成Spring Security之授权概述

文章目录 往期回顾&#xff1a;Spring Boot集成Spring Security专栏及各章节快捷入口前言一、授权概述二、用户权限三、用户授权流程三、Spring Security授权方式1、请求级别授权2、方法级别授权 往期回顾&#xff1a;Spring Boot集成Spring Security专栏及各章节快捷入口 Spr…...

python之Flask入门—路由参数

语法&#xff1a; /routerName/<string:parameter_name> 其中&#xff1a;routerName代表路由名称<>中的string是参数类型&#xff0c;parameter_name为参数名称 参数类型&#xff1a; &#xff08;1&#xff09; string 接收任何没有斜杠&#xff08;/&#x…...

txt地图格式处理

1、txt地图格式 [属性描述] 坐标系2000国家大地坐标系 几度分带3 投影类型高斯克吕格 计量单位米 带号38 精度0.001 转换参数,,,,,, [地块坐标] 5,475.888,1,测试地块1,面,J50G077061,公路用地,地下, J1,1,113.22222222222222,23.129111721551794 J2,1,113.2722314…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...