【算法】【优选算法】优先级队列
目录
- 一、1046.最后一块石头的重量
- 二、703. 数据流中的第 K 大元素
- 三、692. 前 K 个⾼频单词
- 四、295. 数据流的中位数

一、1046.最后一块石头的重量
题目链接:1046.最后一块石头的重量
题目描述:
题目解析:
- 题意就是让我们拿出提供的数组的最大两个值,大减小作差,将差值再放入数组,直到数组空了或者只有一个元素为止。
解题思路:
- 题目要求我们在一个乱序的数组中找最大两个值,我们首先想到数组排序,但是由于我们还需要将差值放入数组,我们放一次就需要排序一次。
- 使用优先级队列,大根堆,开销会小一些,我们只需要每次拿堆顶元素即可。
解题代码:
//时间复杂度 O(n)
//空间复杂度 O(n)
class Solution {public int lastStoneWeight(int[] stones) {//创建大根堆PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> b - a);//入堆for(int i = 0; i < stones.length; i++)queue.offer(stones[i]);//执行逻辑while(!queue.isEmpty() && queue.size() != 1) {int y = queue.poll();int x = queue.poll();queue.offer(y-x); }//返回值return queue.isEmpty() ? 0 : queue.poll();}
}
二、703. 数据流中的第 K 大元素
题目链接:703. 数据流中的第 K 大元素
题目描述:
题目解析:
- 给我们一个数组和一个数K,让我们在使用类的add方法后,返回数组中的第K大的数。
解题思路: - 我们使用一个大小为K的小根堆,那么我们剩下在堆中的数,就是数组中第K大到最大的值。
- 返回数组中的第K大的数,就是当前的堆顶。
解题代码:
//时间复杂度 O(nLogK)
//空间复杂度 O(K)
class KthLargest {PriorityQueue<Integer> heap;int param_1;public KthLargest(int k, int[] nums) {heap = new PriorityQueue<Integer>();param_1 = k;for(int i = 0; i < nums.length; i++) {heap.offer(nums[i]);if(heap.size() > param_1) {heap.poll();}}}public int add(int val) {heap.offer(val);if(heap.size() > param_1) {heap.poll();}return heap.peek();}
}
三、692. 前 K 个⾼频单词
题目链接:692. 前 K 个⾼频单词
题目描述:
题目解析:
- 给我们一个words的字符串数组,让我们返回数组中出现的频率次数最多到第K多的字符串。
- 当出现频次相同的时候,就直接按照字典顺序,字母前到后比较大小,大在前。
解题思路:
- 我们使用一个hash表,记录下字符串与其出现的次数。
- 在使用一个大小为K的堆,当我们的频次就是hash表中的value相同的时候,我们使用compare比较大小,创建的是大根堆,其余比较频次是小根堆。总体上看还是一个小根堆。
- 最后一次取出堆中的字符串即可,但是由于返回值又是从小到大,最后将结果数组逆序即可。
解题代码:
//时间复杂度:O(NLogK)
//空间复杂U度:O(N)
class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String, Integer> hash = new HashMap<>();PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>((a,b) -> {//频次相同大根堆if(a.getValue().equals(b.getValue())) {return b.getKey().compareTo(a.getKey());}//小根堆return a.getValue() - b.getValue();});//hash初始化for( String s : words) {hash.put(s, hash.getOrDefault(s ,0) + 1);}//入堆for(Map.Entry<String, Integer> e : hash.entrySet()) {heap.offer(new Pair<>(e.getKey(),e.getValue()));if(heap.size() > k) {heap.poll();}}//结果处理List<String> ret = new ArrayList<String>();while(!heap.isEmpty()) {ret.add(heap.poll().getKey());}//逆置Collections.reverse(ret);return ret;}
}
四、295. 数据流的中位数
题目链接:295. 数据流的中位数
题目描述:
- 就是让我们实现一个类,有初始化,添加元素(每次添加一个),查看元素中位数
题目解析:
- 我们只需要每次拿取类中的元素的时候,能够直接拿到中位数即可。
- 我们可以使用两个堆,小根堆记录数的中位数之后的部分,大根堆记录中位数的前半部分。
- 这样当元素个数是偶数个的时候,我们直接拿到两个堆的堆顶元素即可。为奇数个元素的时候,直接取出堆元素多的那个的堆顶元素即可。
解题思路:
- 我们使用两个堆,一个大根堆,一个小根堆,在记录下当前的元素个数。
- 当插入元素后,元素个数为偶数:
-
- 当插入元素比大根堆堆顶元素大:
-
-
- 大根堆中元素个数比小根堆多:直接将待插入元素插入小根堆即可。
-
-
-
- 大根堆中元素个数比小根堆少:将小根堆堆顶元素和待插入元素较小值,插入大根堆。另一个给小根堆。
-
-
- 当插入元素比大根堆堆顶元素小:
-
-
- 大根堆中元素个数比小根堆多:将大根堆堆顶元素插入小根堆。待插入元素给大根堆。
-
-
-
- 大根堆中元素个数比小根堆少:直接将待插入元素插入大根堆即可。
-
- 当插入元素后,元素个数为奇数:
-
- 当插入元素比大根堆堆顶元素大:插入小根堆。
-
- 当插入元素比大根堆堆顶元素小:插入大根堆。
解题代码:
//时间复杂度:O(LogN)
//空间复杂度:O(N)
class MedianFinder {//列表中元素个数int n = 0;//大根堆记录前半部分值PriorityQueue<Integer> big;//小根堆记录后半部分值PriorityQueue<Integer> little;public MedianFinder() {big = new PriorityQueue<>((a,b) ->{return b-a;});little = new PriorityQueue<>();}public void addNum(int num) {n += 1;if(n == 1 ) {big.offer(num);return;}//元素个数为偶数,比前面的大if(n % 2 == 0 && big.peek() <= num) {//保持前后数据平衡if(big.size() < little.size()) {//比后面小if(!little.isEmpty() && little.peek() >= num) {big.offer(num);}else {int tmp = little.poll();big.offer(tmp);little.offer(num);}}else {little.offer(num);}return;} //元素个数为偶数,比前面的小if(n % 2 == 0 && big.peek() > num) {//保持前后数据平衡if(big.size() < little.size()) {big.offer(num);}else {int tmp = big.poll();big.offer(num);little.offer(tmp);}return;} //元素个数为奇数,比前面小if(n % 2 != 0 && big.peek() >= num) {big.offer(num);} else {little.offer(num);}}public double findMedian() {if(n % 2 == 0) {return (double)((big.peek() + little.peek())/ 2.0);}if(big.size() > little.size()) {return big.peek();} else {return little.peek();}}
}
相关文章:
【算法】【优选算法】优先级队列
目录 一、1046.最后一块石头的重量二、703. 数据流中的第 K 大元素三、692. 前 K 个⾼频单词四、295. 数据流的中位数 一、1046.最后一块石头的重量 题目链接:1046.最后一块石头的重量 题目描述: 题目解析: 题意就是让我们拿出提供的数组…...
PaddleOCR + Flask 构建 Web OCR 服务实战
1、前言 随着图像识别技术的发展,OCR(光学字符识别)已经成为很多应用场景中的基础能力。PaddleOCR 是百度开源的一个高性能 OCR 工具库,支持中英文、多语言、轻量级部署等特性。 而 Flask 是一个轻量级的 Python Web 框架,非常适合快速构建 RESTful API 或小型 Web 应用…...
openapi-generator-maven-plugin自动生成HTTP远程调用客户端
Java开发中调用http接口的时候,有很多可选的技术方案,比如:HttpURLConnection、RestTemplate、WebClient、Feign、Retrofit、Okhttp等,今天我们来看一个更优的技术方案OpenAPI Generator(http://openapi-generator.tech/) OpenAP…...
ms-swift 部分命令行参数说明
参考链接 命令行参数 — swift 3.6.0.dev0 文档 Qwen Chat num_train_epochs 训练的epoch数,默认为3 假设你有 1000 条训练样本,并且设置了: num_train_epochs 3 这意味着: 模型会完整地遍历这 1000 条数据 3 次。每一次…...
【学习笔记】深入理解Java虚拟机学习笔记——第10章 前端编译与优化
第10章 前端编译与优化 10.1 概述 1>前端编译器:Javac命令。 【.java文件->.class文件】 2>即时编译器:Hotspot.C1.C2 【.class文件->机器码】 3>提前编译器:JDK的Jaotc等【.java->机器码】 10.2 Javac 编译器 10.2.1 …...
删除node并且重装然后重装vue
参考第一篇文章 node.js卸载与安装超详细教程_node卸载重装-CSDN博客 第二篇文章安装vue Vue安装与配置教程(非常详细)_安装vue-CSDN博客...
Flink源码阅读环境准备全攻略:搭建高效探索的基石
想要深入探索Flink的底层原理,搭建一套完整且适配的源码阅读环境是必经之路。这不仅能让我们更清晰地剖析代码逻辑,还能在调试过程中精准定位关键环节。接下来,结合有道云笔记内容,从开发工具安装、源码获取导入到调试配置&#x…...
【破局痛点,赋能未来】领码 SPARK:铸就企业业务永续进化的智慧引擎—— 深度剖析持续演进之道,引领数字化新范式
摘要 在瞬息万变的数字时代,企业对业务连续性、敏捷创新及高效运营的需求日益迫切。领码 SPARK 融合平台,秉持“持续演进”这一核心理念,以 iPaaS 与 aPaaS 为双擎驱动,深度融合元数据驱动、智能端口调度、自动化灰度切换、AI 智…...
Flink SQL Connector Kafka 核心参数全解析与实战指南
Flink SQL Connector Kafka 是连接Flink SQL与Kafka的核心组件,通过将Kafka主题抽象为表结构,允许用户使用标准SQL语句完成数据读写操作。本文基于Apache Flink官方文档(2.0版本),系统梳理从表定义、参数配置到实战调优…...
Linux 服务器运维:磁盘管理与网络配置
🤵♂️ 个人主页:布说在见 ✍🏻作者简介: 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞👍🏻 收藏…...
PyTorch 入门学习笔记
目录 1 张量 1)张量的初始化和属性 2)张量操作 3)使用 NumPy 进行桥接 2 torch.autograd 1)背景 2)在 PyTorch 中的使用 3)Autograd 的微分机制 4)计算图原理 3 神经网络 1ÿ…...
9大策略深度解析MySQL多表JOIN性能优化
一、多表JOIN的现实挑战 在实际开发中,MySQL多表JOIN场景主要源于两类场景: • 历史遗留系统:老代码中未严格遵循范式设计的SQL语句• 数据库迁移:从Oracle迁移至MySQL时保留的复杂关联查询 这类操作潜藏多重风险: …...
CSS 逐帧动画
CSS 逐帧动画实现指南 逐帧动画(frame-by-frame animation)是一种通过快速连续显示一系列静态图像来创造运动效果的技术。以下是使用CSS实现逐帧动画的几种方法。 1. 使用 steps() 计时函数 这是实现逐帧动画最常用的方法,通过animation-timing-function的steps(…...
UE5 游戏模板 —— ThirdPersonGame
UE5 游戏模板 —— ThirdPersonGame 前言一、初始化旋转控制参数1.参数一2.参数二3.参数三4.参数四 二、输入系统总结 前言 有了前面的铺垫,第三人称模板简直是手到擒来了,我们只需要注意一些初始化的变量是做什么的即可,因为UE的Character …...
java中关于异步转同步的一些解决方案的对比与思考。【spring mvc堵塞式】
文章目录 1、Spring MVC堵塞式编程中的技术方案a) 最简单的方案,使用 DeferredResult 代码如下,代码解读:最终控制台输出如下。用户收到的结果 b) 上点难度,使用redis监听事件,根据事件的不同返回不同的数据…...
【数据结构与算法】数据结构核心概念系统梳理
第一章 绪论:基础概念体系 🚩算法:问题求解步骤的描述。 🚩非递归的算法效率更高。 1.1 逻辑结构 vs 存储结构 维度逻辑结构存储结构(物理结构)定义数据元素之间的逻辑关系数据结构在计算机中的实现方式分类线性/树形/图/集合顺序/链式/索引/散列独立性独立于存储结构…...
《HTTP权威指南》 第7章 缓存
带着问题学习: 缓存如何提高性能如何衡量缓存的有效性缓存置于何处作用最大HTTP如何保持缓存副本的新鲜度缓存如何与其他缓存及服务器通信 web缓存是可以自动保存常见文档副本的HTTP设备。 缓存优点 减少冗余的数据传输,节省网络费用缓解网络瓶颈问题&…...
【Zephyr 系列 28】MCU 闪存文件系统详解:LittleFS + NVS + 块设备设计实战
🧠关键词:Zephyr 文件系统、LittleFS、NVS、Flash 分区、嵌入式存储、断电保护、wear leveling 📌 1. 为什么 MCU 上需要文件系统? 在嵌入式开发中,很多开发者起初直接操作 Flash 保存参数,但随着需求增长…...
ICML 2025 | 时间序列(Time Series)论文总结
ICML 2025将在2025年7月13日至7月19日(周六)在温哥华会议中心举行,本文总结了ICML 2025有关时间序列(Time Series)相关文章,共计63篇。 时间序列Topic:预测,分类,异常检测,生成&…...
理解后端开发中的中间件(以gin框架为例)
中间件(Middleware)是后端开发中的一个核心概念,它在请求(Request)和响应(Response)之间扮演着桥梁角色。以下是关于中间件的详细解释: 基本概念 中间件是在请求到达最终处理程序之前或响应返回客户端之前执行的一系列函数或组件。它可以: 访…...
【分布式技术】Bearer Token以及MAC Token深入理解
Bearer Token以及MAC Token深入理解 **Bearer Token 详解****1. 什么是 Bearer Token?****2. Bearer Token 的构建详情****(1)生成流程****(2)Token 示例(JWT)****(3)Tok…...
WebRTC(七):媒体能力协商
目的 在 WebRTC 中,每个浏览器或终端支持的音视频编解码器、分辨率、码率、帧率等可能不同。媒体能力协商的目的就是: 确保双方能“听得懂”对方发的媒体流;明确谁发送、谁接收、怎么发送;保障连接的互操作性和兼容性。 P2P的基…...
(线性代数最小二乘问题)Normal Equation(正规方程)
Normal Equation(正规方程) 是线性代数中的一个重要概念,主要用于解决最小二乘问题(Least Squares Problem)。它通过直接求解一个线性方程组,找到线性回归模型的最优参数(如权重或系数ÿ…...
【机器学习】数学基础——标量
目录 一、标量的定义 二、标量的核心特征:无方向的纯粹量级 2.1 标量 vs 矢量 直观对比 三、 标量的数学本质:零阶张量 3.1 张量阶数金字塔 3.2 标量的数学特性 四、 现实世界的标量图谱 4.1 常见标量家族 4.2 经典案例解析 五、 标量的运算奥秘…...
基于python代码的通过爬虫方式实现TK下载视频(2025年6月)
Tk的视频页面通常需要登录才能获取完整数据,但通过构造匿名游客的请求,我们可以绕过登录限制,提取视频的元信息(如标题、ID和播放地址)。核心思路如下: 构造匿名Cookie:通过模拟浏览器的请求,获取Tk服务器分配的游客Cookie。解析网页:利用BeautifulSoup解析HTML,定位…...
Go 语言的堆糖图片爬虫
基于 Go 语言的堆糖图片爬取探索之旅 在互联网的浩瀚海洋中,堆糖网以其丰富多样的高清图片、美图壁纸等内容吸引了众多用户。对于图片爱好者来说,能高效获取心仪的图片资源无疑是一件极具吸引力的事情。今天,就带大家走进一段基于 Go 语言的…...
python+uni-app基于微信小程序的儿童安全教育系统
文章目录 具体实现截图本项目支持的技术路线源码获取详细视频演示:文章底部获取博主联系方式!!!!本系统开发思路进度安排及各阶段主要任务java类核心代码部分展示主要参考文献:源码获取/详细视频演示 ##项目…...
DAY 39 图像数据与显存
图像数据的格式:灰度和彩色数据模型的定义显存占用的4种地方 模型参数梯度参数优化器参数数据批量所占显存神经元输出中间状态 batchisize和训练的关系 import torch import torch.nn as nn import torch.optim as optim from torch.utils.data import DataLoader ,…...
ELK搭建
1、elasticsearch和kibana搭建配置见 https://blog.csdn.net/yh_zeng2/article/details/148812447?spm1001.2014.3001.5501 2、logstash 下载 下载和elasticsearch版本一致的logstash,下载地址: Past Releases of Elastic Stack Software | Elastic …...
【ELK(Elasticsearch+Logstash+Kibana) 从零搭建实战记录:日志采集与可视化】
ELK(ElasticsearchLogstashKibana) 从零搭建实战记录:日志采集与可视化 本文记录了我在搭建ELK(Elasticsearch, Logstash, Kibana)技术栈时的完整实战过程。使用Docker Compose快速搭建了ELK服务端(监控主机),并通过Filebeat实现…...
反无人机系统:技术利刃如何守护低空安全?
反无人机系统:技术利刃如何守护低空安全? ——从军事防御到城市安防的全景解析 一、技术体系:从“电磁软杀伤”到“激光硬摧毁”的立体防御网 反无人机技术本质是一场“降维打击”:用百万级防御系统对抗千元级消费无人机。当前…...
第十章——8天Python从入门到精通【itheima】-102-Python基础综合案例-数据可视化(pyecharts的入门使用+数据处理)
目录 102节——pyecharts的入门使用 1.学习目标 2.pyecharts入门——基础折线图 3.pyecharts的配置对象有哪些? 4.全局配置——set_global_opts 5.小节总结 103节——数据处理 1.学习目标 2.无法继续关于第一阶段的pyecharts的相关学习 因为关于JSON数据获…...
Neo4j 中存储和查询数组数据的完整指南
Neo4j 中存储和查询数组数据的完整指南 图形数据库 Neo4j 不仅擅长处理节点和关系,还提供了强大的数组(Array)存储和操作能力。本文将全面介绍如何在 Neo4j 中高效地使用数组,包括存储、查询、优化以及实际应用场景。 数组在 Neo4j 中的基本使用 数组…...
云原生/容器相关概念记录
文章目录 网络与虚拟化技术云平台与架构容器与编排容器网络方案性能优化与工具硬件与协议 网络与虚拟化技术 P4可编程网关 P4: Programming Protocol-independent Packet Processors一种基于P4语言的可编程网络设备,支持自定义数据包处理逻辑。P4可编程技术详解&am…...
uni-app项目实战笔记21--uniapp缓存的写入和读取
一、缓存的写入 uni.setStorageSync("storageClassList",classifyList.value) 二、缓存的读取,如果缓存不存在,则返回空数组 const storageClassList uni.getStorageSync("storageClassList") || []; 三、对读取到的数据进行转…...
操作系统概述
覆盖了操作系统概述、运行机制、中断、异常、操作系统的五大结构、虚拟机。 借鉴:王道、我的好朋友杨某、我的笔记。 一、操作系统概念 概念 1.操作系统体现了封装思想 由于底层硬件只接受二进制的指令不方便用户操作,所以操作系统把这些封装成简易的…...
探索数据的力量:Elasticsearch中指定链表字段的统计查询记录
目录 一、基本的数据结构说明 二、基本的统计记录 (一)统计当前索引中sellingProducts的所有类型 (二)检索指定文档中sellingProducts的数据总量 (三)检索指定文档中sellingProducts指定类型的数量统计…...
【Datawhale组队学习202506】YOLO-Master task03 IOU总结
系列文章目录 task01 导学课程 task02 YOLO系列发展线 文章目录 系列文章目录前言1 功能分块1.1 骨干网络 Backbone1.2 颈部网络 Neck1.3 头部网络 Head1.3.1 边界框回归头1.3.2 分类头 2 关键概念3 典型算法3.1 NMS3.2 IoU 总结 前言 Datawhale是一个专注于AI与数据科学的开…...
C/C++数据结构之静态数组
概述 静态数组是C/C中一种基础的数据结构,它允许用户在编译时便确定数组的大小,并分配固定数量的连续存储空间来存放相同类型的元素。静态数组的主要特点是:其大小在声明时就必须指定,且在其生命周期内保持不变。这也意味着&#…...
pyqt f-string
文章目录 一、f-string的基本语法二、代码中的具体应用拼接效果 三、f-string的核心优势四、与其他字符串格式化方式的对比五、在Qt程序中的实际作用六、扩展用法:在f-string中添加格式说明 Python的 f-string(格式化字符串字面值) 特性&…...
夏普 AR-2348SV 打印机信息
基本信息:这是一款黑白 A3 激光多功能数码复合机,可实现打印、复印、扫描功能。性能参数 打印 / 复印速度:23 张 / 分钟。分辨率:600x600dpi,能确保文字和图像清晰。最大打印 / 复印尺寸:A3。纸张支持&…...
跨个体预训练与轻量化Transformer在手势识别中的应用:Bioformer
目录 一、从深度学习到边缘部署,手势识别的新突破 (一)可穿戴设备 边缘计算 个性化医疗新可能 (二)肌电信号(sEMG):手势识别的关键媒介 (三)挑战&#…...
探索常识性概念图谱:构建智能生活的知识桥梁
目录 一、知识图谱背景介绍 (一)基本背景 (二)与NLP的关系 (三)常识性概念图谱的引入对比 二、常识性概念图谱介绍 (一)常识性概念图谱关系图示例 (二)…...
人人都是音乐家?腾讯开源音乐生成大模型SongGeneration
目录 前言 一、SongGeneration 带来了什么? 1.1 文本控制与风格跟随:你的想法,AI 精准实现 1.2 多轨生成:从“成品”到“半成品”的巨大飞跃 1.3 开源:推倒“高墙”,共建生态 二、3B 参数如何媲美商业…...
一,python语法教程.内置API
一,字符串相关API string.strip([chars])方法:移除字符串开头和结尾的空白字符(如空格、制表符、换行符等),它不会修改原始字符串,而是返回一个新的处理后的字符串 chars(可选)&…...
python中学物理实验模拟:凸透镜成像和凹透镜成像
python中学物理实验模拟:凸透镜成像和凹透镜成像 凸透镜成像 凸透镜是指中间厚、边缘薄的透镜。它对光线有会聚作用,即光线通过凸透镜后会向主光轴方向偏折。 成像原理 基于光的折射,平行于主光轴的光线经凸透镜折射后会聚于焦点ÿ…...
【AGI】突破感知-决策边界:VLA-具身智能2.0
突破感知-决策边界:VLA-具身智能2.0 (一)技术架构核心(二)OpenVLA:开源先锋与性能标杆(三)应用场景:从实验室走向真实世界(四)挑战与未来方向&…...
2D曲线点云平滑去噪
2D曲线点云,含许多噪声,采用类似移动最小二乘的方法(MLS)分段拟合抛物线并投影至抛物线,进行点云平滑去噪。 更通俗的说法是让有一定宽度的曲线点云,变成一条细曲线上的点。 分两种情况进行讨论: 1&#…...
靶场(二十一)---小白心得靶场体会---DVR4
先看端口,看到了一个dvr的服务,老规矩只要有服务就先去看看 PORT STATE SERVICE VERSION 22/tcp open ssh Bitvise WinSSHD 8.48 (FlowSsh 8.48; protocol 2.0; non-commercial use) | ssh-hostkey: | 3072 21:25:f0:53:b4…...
Qt + C++ 入门2(界面的知识点)
补充前面没有说到的一点就是,qt的页面你可以用qt自带的也就是前面所说的自动生成.UI文件生成前端所谓的界面,然后往里面拖控件就可以了,这个UI界面非常的适合用于新手,以及某些软件少量的界面应用 。但是有一个难点就是后期这个UI…...