春招百题--堆
一、堆的定义
二、堆(优先队列)
堆通常用于实现优先队列(priority_queue),大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看,我们可以将“优先队列”和“堆”看作等价的数据结构。
堆的常见用法:
/* 初始化堆 */
// 初始化小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 初始化大顶堆
priority_queue<int, vector<int>, less<int>> maxHeap;/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);/* 获取堆顶元素 */
int peek = maxHeap.top(); // 5/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1/* 获取堆大小 */
int size = maxHeap.size();/* 判断堆是否为空 */
bool isEmpty = maxHeap.empty();/* 输入列表并建堆 */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());
三、堆的常见应用
- 优先队列:堆通常作为实现优先队列的首选数据结构,其入队和出队操作的时间复杂度均为 0(logn) ,而建队操作为 0(n),这些操作都非常高效。
- 堆排序:给定一组数据,我们可以用它们建立一个堆,然后不断地执行元素出堆操作,从而得到有序数据。
- 获取最大的 K 个元素:这是一个经典的算法问题,同时也是一种典型应用,例如选择热度前 10 的新闻作为微博热搜,选取销量前 10 的商品等。
四、具体思路top-k问题:
- 初始化一个小顶堆,其堆顶元素最小。
- 先将数组的前 k 个元素依次入堆。
- 从第 k+1 个元素开始,若当前元素大于堆顶元素,则将堆顶元素出堆,并将当前元素入堆。
- 遍历完成后,堆中保存的就是最大的 k个元素。
/* 基于堆查找数组中最大的 k 个元素 */
priority_queue<int, vector<int>, greater<int>> topKHeap(vector<int> &nums, int k) {// 初始化小顶堆priority_queue<int, vector<int>, greater<int>> heap;// 将数组的前 k 个元素入堆for (int i = 0; i < k; i++) {heap.push(nums[i]);}// 从第 k+1 个元素开始,保持堆的长度为 kfor (int i = k; i < nums.size(); i++) {// 若当前元素大于堆顶元素,则将堆顶元素出堆、当前元素入堆if (nums[i] > heap.top()) {heap.pop();heap.push(nums[i]);}}return heap;
}
总共执行了 n 轮入堆和出堆,堆的最大长度为 k ,因此时间复杂度为 0(nlogk)。该方法的效率很高,当 k 较小时,时间复杂度趋向0(n) ;当k 较大时,时间复杂度不会超过 0(nlogn) 。
另外,该方法适用于动态数据流的使用场景。在不断加入数据时,我们可以持续维护堆内的元素,从而实现最大的 k个元素的动态更新
五、习题:
215. 数组中的第K个最大元素
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//建大顶堆priority_queue<int,vector<int>,greater<int>>heap;int n=nums.size();for(int i=0;i<k;i++){heap.push(nums[i]);}for(int i=k;i<n;i++){if(nums[i]>heap.top()){heap.pop();heap.push(nums[i]);} }return heap.top();}
};
264. 丑数 II
给你一个整数 n
,请你找出并返回第 n
个 丑数 。
丑数 就是质因子只包含 2
、3
和 5
的正整数。
思路:如果x是丑数,则2x、3x、5x也是丑数。所以我们不妨使用一个优先队列,存储这些丑数。
每次取出堆顶元素 x,则 x 是堆中最小的丑数,由于 2x,3x,5x 也是丑数,因此将 2x,3x,5x加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素,可以使用哈希集合去重,避免相同元素多次加入堆。
哈希去重:
unordered_set<long> seen;//建立哈希表
//seen.count(x)//对x元素计数。if(!seen.count(x))//x此时一个都没有
seen.insert(x);//插入到哈希表中,此时数量就为一了
class Solution {
public:int nthUglyNumber(int n) {//哈希表去重unordered_set<long> seen;vector<int>factors={2,3,5};priority_queue<long,vector<long>,greater<long>>heap;seen.insert(1L);heap.push(1L);int ugly=0;for(int i=0;i<n;i++){long curr=heap.top();heap.pop();ugly=(int)curr;for(int factor:factors){long next=curr*factor;if(!seen.count(next)){seen.insert(next);heap.push(next);}}}return ugly;}
};
另外一个方法:. - 力扣(LeetCode)
相关文章:
春招百题--堆
一、堆的定义 二、堆(优先队列) 堆通常用于实现优先队列(priority_queue),大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看,我们可以将“优先队列”和“堆”看作等价的数据结构。 堆的…...
全志A40i android7.1 移植wifi驱动的一般流程
一,问题分析 一般情况下移植一款模组,会涉及到驱动,firmware, hal层,方案端的适配。 下面以RTL8723ds为例详细列出移植的通用步骤。 二,移植步骤 1. 移植Wi-Fi驱动 从RTL原厂或者已经支持的其他把内核版本中获取驱动…...
Qt——Qt绘图之QPainter的使用总结(使用paintEvent实现旋转图片效果)
【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...
Day83:服务攻防-开发组件安全JacksonFastJson各版本XStreamCVE环境复现
目录 J2EE-组件Jackson-本地demo&CVE 代码执行 (CVE-2020-8840) 代码执行 (CVE-2020-35728) J2EE-组件FastJson-本地demo&CVE FastJson < 1.2.24 FastJson < 1.2.47 FastJson < 1.2.80 (利用条件比较苛刻) J2EE-组件XStream-靶场&CVE …...
【QT+QGIS跨平台编译】056:【pdal_kazhdan+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
点击查看专栏目录 文章目录 一、pdal_kazhdan介绍二、pdal下载三、文件分析四、pro文件五、编译实践一、pdal_kazhdan介绍 pdal_kazhdan 是 PDAL(Point Data Abstraction Library)相关的 Kazhdan 算法的实现。PDAL 是一个用于处理和分析点云数据的开源库,而 Kazhdan 算法通常…...
泰坦尼克号幸存者数据分析
泰坦尼克号幸存者数据分析 1、泰坦尼克号数据集2、数据集加载与概览3、泰坦尼克号幸存者数据分析4、哪些人可能成为幸存者? 1、泰坦尼克号数据集 泰坦尼克号的沉没是世界上最严重的海难事故之一,造成了大量的人员伤亡。这是一艘号称当时世界上最大的邮轮…...
Memcached 教程之 PHP 连接 Memcached 服务(十)
PHP 连接 Memcached 服务 在前面章节中我们已经介绍了如何安装 Memcached 服务,接下来我们为大家介绍 PHP 如何使用 Memcached 服务。 PHP Memcache 扩展安装 PHP Memcache 扩展包下载地址:PECL :: Package :: memcache,你可以下载最新稳定…...
【zlm】音视频流与音频流合并的设计
目录 设想一 设想二 方案三 关键技术 测试语句 测试脚本 参考文档 设想一 //开始录制_option.mp4_save_path custom_path;_option.mp4_max_second max_second;vector<Track::Ptr> mytracks getTracks();auto src MediaSource::find( DEFAULT_VHOST, "1&quo…...
typescript的工作流
先coding code.ts代码,由tsc编译code.ts生成code.js格式 npm install —save-dev lite-server 是用来安装轻量级的服务器,只是用来开发的一个服务器,真正到生产环境中时可能会使用类似于Apache的server或者汤姆猫一类的服务器,安…...
MATLAB下载与安装详细教程:从官方获取到成功启动
引言 MATLAB(MATrix LABoratory)作为一款全球知名的高级数值计算与数据分析平台,以其强大的矩阵运算能力、丰富的内置函数库以及直观易用的图形用户界面,深受科研人员、工程师和学生群体的青睐。无论是进行复杂的数学建模、信号处…...
【随笔】Git 高级篇 -- 分离 HEAD(十一)
💌 所属专栏:【Git】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! 💖 欢迎大…...
mac、windows 电脑安装使用多个版本的node
我们为啥要安装多个不同版本的node? 开发旧项目时,使用低版本Nodejs。开发新项目时,需使用高版本Node.js。可使用n同时安装多个版本Node.js,并切换到指定版本Node.js。 mac电脑安装 一、全局安装 npm install -g n 二、mac电脑…...
vue 浅解watch cli computed props ref vue slot axios nexttick devtools说明使用
Vue.js 是一个强大的前端框架,它提供了很多有用的功能和工具。你提到的这些特性(watch、cli、computed、props、ref、slot、axios、nextTick、devtools)在 Vue 中各自扮演着不同的角色。下面我会逐一解释这些特性如何在 Vue 中使用࿱…...
Unity自定义框架(1)-----------单例模式
前言: Unity作为一款强大的游戏开发引擎,其基础框架的设计对于项目的结构和性能有着重要的影响。其中,单例模式是一种常用的设计模式,用于确保一个类只有一个实例,并提供一个全局访问点。 什么是单例模式?…...
04-自媒体文章-自动审核
自媒体文章-自动审核 1)自媒体文章自动审核流程 1 自媒体端发布文章后,开始审核文章 2 审核的主要是审核文章的内容(文本内容和图片) 3 借助第三方提供的接口审核文本 4 借助第三方提供的接口审核图片,由于图片存储到minIO中&…...
LeetCode-热题100:763. 划分字母区间
题目描述 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。 注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。…...
IDEA2023创建SpringMVC项目
✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: 开发环境篇 ✨特色专栏: M…...
ubuntu-server部署hive-part2-安装hadoop
参照 https://blog.csdn.net/qq_41946216/article/details/134345137 操作系统版本:ubuntu-server-22.04.3 虚拟机:virtualbox7.0 安装hadoop 下载上传 下载地址 https://archive.apache.org/dist/hadoop/common/hadoop-3.3.4/ 以root用…...
Python深度学习032:conda操作虚拟环境env的全部命令
文章目录 创建和管理环境环境列表和检查环境的保存与复制更新环境清理 CondaConda 是一个开源的包管理器和环境管理器,可以用于安装、运行和升级包和环境。 使用 Conda,你可以创建、导出、列出、删除和更新环境,这些环境可以包含不同版本的 Python 以及/或软件包。 下面列出…...
使用Java拓展本地开源大模型的网络搜索问答能力
背景 开源大模型通常不具备最新语料的问答能力。因此需要外部插件的拓展,目前主流的langChain框架已经集成了网络搜索的能力。但是作为一个倔强的Java程序员,还是想要用Java去实现。 注册SerpAPI Serpapi 提供了多种搜索引擎的搜索API接口。 访问 Ser…...
Mybatis——一对多关联映射
一对多关联映射 一对多关联映射有两种方式,都用到了collection元素 以购物网站中用户和订单之间的一对多关系为例 collection集合的嵌套结果映射 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import java.util.List;Data public cla…...
Pytorch实用教程:TensorDataset和DataLoader的介绍及用法示例
TensorDataset TensorDataset是PyTorch中torch.utils.data模块的一部分,它包装张量到一个数据集中,并允许对这些张量进行索引,以便能够以批量的方式加载它们。 当你有多个数据源(如特征和标签)时,TensorD…...
uni-app如何实现高性能
这篇文章主要讲解uni-app如何实现高性能的问题? 什么是uni-app? 简单说一下什么是uni-app,uni-app是继承自vue.js,对vue做了轻度定制,并且实现了完整的组件化开发,并且支持多端发布的一种架构,…...
docker 应用部署
参考:docker 构建nginx服务 环境 Redhat 9 步骤: 1、docker部署MySQL 安装yum 工具包 [rootadmin ~]# yum -y install yum-utils.noarch 正在更新 Subscription Management 软件仓库。 无法读取客户身份本系统尚未在权利服务器中注册。可使用 subscription-…...
java.awt.FontFormatException: java.nio.BufferUnderflowException
Font awardFont Font.createFont(Font.TRUETYPE_FONT, awardFontFile).deriveFont(120f).deriveFont(Font.BOLD);使用如上语句创建字体时出现问题。java.awt.FontFormatException: java.nio.BufferUnderflowException异常表明在处理字体数据时出现了缓冲区下溢(Buf…...
C++ 枚举类型 ← 关键字 enum
【知识点:枚举类型】● 枚举类型(enumeration)是 C 中的一种派生数据类型,它是由用户定义的若干枚举常量的集合。 ● 枚举元素作为常量,它们是有值的。C 编译时,依序对枚举元素赋整型值 0,1,2,3,…。 下面代…...
MySQL故障排查与优化
一、MySQL故障排查 1.1 故障现象与解决方法 1.1.1 故障1 1.1.2 故障2 1.1.3 故障3 1.1.4 故障4 1.1.5 故障5 1.1.6 故障6 1.1.7 故障7 1.1.8 故障8 1.1.9 MySQL 主从故障排查 二、MySQL优化 2.1 硬件方面 2.2 查询优化 一、MySQL故障排查 1.1 故障现象与解决方…...
如何做一个知识博主? 善用互联网检索
Google 使用引号: 使用双引号将要搜索的短语括起来,以便搜索结果中只包含该短语。例如,搜索 "人工智能" 将只返回包含该短语的页面。 排除词汇: 在搜索中使用减号 "-" 可以排除特定词汇。例如,搜索 "苹果 -手机" 将返回关于苹果公司的结果,但…...
《QT实用小工具·十》本地存储空间大小控件
1、概述 源码放在文章末尾 本地存储空间大小控件,反应电脑存储情况: 可自动加载本地存储设备的总容量/已用容量。进度条显示已用容量。支持所有操作系统。增加U盘或者SD卡到达信号。 下面是demo演示: 项目部分代码如下: #if…...
作为一个初学者该如何学习kali linux?
首先你要明白你学KALI的目的是什么,其次你要了解什么是kali,其实你并不是想要学会kali你只是想当一个hacker kali是什么: 只是一个集成了多种渗透工具的linux操作系统而已,抛开这些工具,他跟常规的linux没有太大区别。…...
seo是什么意思啊视频教程/seo优化运营
CListCtrl 类封装“列表视图控件”功能,显示每个包含图标(列表视图中)和标签的收集。除图标和标签外,每一项还能有显示在图标和标签的右边的列中的信息。此控件(以及CListCtrl类)只适用于运行于Windows 95和…...
查网站注册信息/销售管理系统
401. 二进制手表 二进制手表顶部有 4 个 LED 代表小时(0-11),底部的 6 个 LED 代表分钟(0-59)。 每个 LED 代表一个 0 或 1,最低位在右侧。 例如,上面的二进制手表读取 “3:25”。 给定一个…...
自己注册个公司做网站怎么样/阿里巴巴指数查询
简介 django为用户实现防止跨站请求伪造的功能,通过中间件 django.middleware.csrf.CsrfViewMiddleware 来完成。而对于django中设置防跨站请求伪造功能有分为全局和局部。 全局: 中间件 django.middleware.csrf.CsrfViewMiddleware 局部: cs…...
dede跳转到其他网站/网络平台销售
用Zabbix通过JMX方式监控JVM/Tomcat/Weblogic/Websphere/Jboss等转载自:http://www.huilog.com/?p688 JMX(Java Management Extensions,即Java管理扩展)是一个为应用程序、设备、系统等植入管理功能的框架。JMX可以跨越一系列异构…...
广元市剑阁县建设局网站/交换链接网站
public、protected和private这三个java访问权限修饰词在使用时,是置于类中每个成员的定义之前的,无论它是一个域还是一个方法。 一. public 包访问权限,默认访问权限,有时候也表示friendly。意味着当前包中的所有类对那个成员…...
广州铁路投资建设集团网站/平台推广怎么做
i2c-tools i2cdetect 检测在系统上的i2c总线,例如: i2cdetect -l 检测挂载在i2c总线上器件,例如: i2cdetect -r -y 0 (检测i2c-0上的挂载情况) i2cdump 查看器件所有寄存器的值,例如:…...