力扣题目解析--合并k个升序链表
题目
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [1->4->5,1->3->4,2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2:
输入:lists = [] 输出:[]
示例 3:
输入:lists = [[]] 输出:[]
提示:
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i]
按 升序 排列lists[i].length
的总和不超过10^4
代码展示
#include <queue>
using namespace std;struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val; // 最小堆}
};class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, Compare> pq;for (auto& list : lists) {if (list) {pq.push(list);}}ListNode* dummy = new ListNode(0);ListNode* current = dummy;while (!pq.empty()) {ListNode* top = pq.top();pq.pop();current->next = top;current = current->next;if (top->next) {pq.push(top->next);}}return dummy->next;}
};
写者心得
练习中曾经做过合并两个链表的题,然后写者准备加一个循环,就是把他给的这个数组里面的链表提取出来之后再合并起来,但是运行出了bug,于是我就去找到了这样一个和我当初思路截然不同的做法,这个利用的是栈,代码比我当初利用for循环来进行链表合并要少很多
逐行解析
-
自定义比较器:
struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val; // 最小堆} };
- 这是一个自定义的比较器,用于优先队列中的排序。
operator()
定义了比较规则,使得优先队列成为一个最小堆,即队列顶部的节点值是最小的。
-
创建优先队列:
priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
- 使用
priority_queue
创建一个最小堆,存储类型为ListNode*
。 vector<ListNode*>
是优先队列的底层容器。Compare
是自定义的比较器,确保优先队列按节点值从小到大排序。
- 使用
-
初始化优先队列:
for (auto& list : lists) {if (list) { // 检查链表是否为空pq.push(list);} }
- 遍历输入的链表列表
lists
。 - 对于每个链表,检查其是否为空(
if (list)
),如果不为空,则将其头节点加入优先队列。
- 遍历输入的链表列表
-
创建虚拟头节点:
ListNode* dummy = new ListNode(0); ListNode* current = dummy;
- 创建一个虚拟头节点
dummy
,值为 0。 current
指向dummy
,用于构建新的链表。
- 创建一个虚拟头节点
-
合并链表:
while (!pq.empty()) {ListNode* top = pq.top();pq.pop();current->next = top;current = current->next;if (top->next) {pq.push(top->next);} }
- 当优先队列不为空时,进入循环。
- 从优先队列中取出当前最小的节点
top
。 - 将
top
添加到新链表中,即current->next = top
,并移动current
到top
。 - 如果
top
有下一个节点(if (top->next)
),则将top->next
加入优先队列。
-
返回新链表的头节点:
return dummy->next;
- 返回新链表的头节点,即
dummy
的下一个节点。
- 返回新链表的头节点,即
条件的使用
if (list)
:检查链表是否为空。只有非空链表的头节点才会被加入优先队列。if (top->next)
:检查当前节点是否有下一个节点。如果有,则将下一个节点加入优先队列,以继续参与后续的合并操作。
1. 自定义比较器
什么是比较器?
比较器是一个函数对象,用于定义两个对象之间的比较规则。在 C++ 标准库中,许多容器(如 std::sort
、std::priority_queue
)都允许用户自定义比较器。
自定义比较器的例子
struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val; // 最小堆}
};
struct Compare
:定义一个结构体Compare
,用于存储比较逻辑。bool operator()(ListNode* a, ListNode* b)
:重载()
操作符,使其像一个函数一样调用。- 参数
a
和b
是两个ListNode*
类型的指针。 - 返回值
bool
表示a
是否大于b
。 return a->val > b->val;
:如果a
的值大于b
的值,返回true
,否则返回false
。这使得优先队列成为一个最小堆。
- 参数
2. 创建优先队列
什么是优先队列?
优先队列是一种特殊的队列,取出元素的顺序并不是按照进入的顺序,而是根据元素的优先级。在 C++ 中,std::priority_queue
是一个容器适配器,默认情况下是一个最大堆(即队列顶部的元素是最大的)。
创建最小堆的优先队列
priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
priority_queue<ListNode*, vector<ListNode*>, Compare>
:- 第一个模板参数
ListNode*
:优先队列中存储的元素类型。 - 第二个模板参数
vector<ListNode*>
:底层容器,用于存储元素。默认情况下是vector
。 - 第三个模板参数
Compare
:自定义的比较器,用于定义元素的优先级
- 第一个模板参数
相关文章:
力扣题目解析--合并k个升序链表
题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下…...

Linux:调试器-gdb/cgdb
文章目录 一、编译成debug1、-g 选项 二、gdb调试命令1、在CentOS系统下检查安装gdb2、进入gdb模式3、quit 退出gdb4、list (简写 l)显示文件内容5、b 打断点6、 r / run运行程序7、c 让程序直接运行完 三、cgdb1、info b查看打的所有断点2、d 删除断点3…...

『VUE』30. 生命周期的介绍(详细图文注释)
目录 生命周期生命周期的8阶段生命周期小例子总结 欢迎关注 『VUE』 专栏,持续更新中 欢迎关注 『VUE』 专栏,持续更新中 生命周期 每个 Vue 组件实例在创建时都需要经历一系列的初始化步骤,比如设置好数据侦听,编译模板…...
Python 人脸检测:使用 Dlib 和 OpenCV
简介 本文用Python、Dlib 和 OpenCV 库来检测图像中的人脸,并在人脸上绘制矩形框进行窗口显示。 环境准备 在开始之前,请确保您的计算机上已安装 Python。此外,您还需要安装以下库: dlib:一个包含多种机器学习算法…...

【大数据学习 | flume】flume的概述与组件的介绍
1. flume概述 Flume是cloudera(CDH版本的hadoop) 开发的一个分布式、可靠、高可用的海量日志收集系统。它将各个服务器中的数据收集起来并送到指定的地方去,比如说送到HDFS、Hbase,简单来说flume就是收集日志的。 Flume两个版本区别: 1&…...
torch.is_storage()
torch.is_storage() 判断给定的对象是否是一个 PyTorch 存储对象 PyTorch 存储对象:PyTorch 中,存储对象(Storage)是一个低级别的对象,它表示一个存储数据的连续内存块。存储对象不包含任何关于数据如何解释的信息&a…...
2411rust,编译时自动检查配置
原文 Cargo和编译器团队很高兴地宣布,从Rust1.80(或nightly-2024-05-05)开始,会自动检查每个可访问的#[cfg],看看是否与期望的配置名和值匹配. 这帮助验证crate,是否正确处理不同目标平台或函数的条件编译.它确保在期望和使用设置的配置间保持一致,帮助在开发过程的早期抓住潜…...
在 Ubuntu 中用 VSCode 配置 C 语言项目的编译与调试(详解教程)
目录 一、准备工作二、配置 VSCode 的编译任务三、配置 VSCode 的调试任务四、编译与调试流程五、常见问题排查六、总结 在 C 语言开发过程中,调试与编译是不可缺少的环节,而 VSCode(Visual Studio Code)作为一个强大且轻量级的编…...

MATLAB绘制克莱因瓶
MATLAB绘制克莱因瓶 clc;close all;clear all;warning off;% clear all rand(seed, 100); randn(seed, 100); format long g;% Parameters u_range linspace(0, 2*pi, 100); v_range linspace(0, pi, 50); [U, V] meshgrid(u_range, v_range);% Parametric equations for t…...

HTML5实现趣味飞船捡金币小游戏(附源码)
文章目录 1.设计来源1.1 主界面1.2 游戏中界面1.2 飞船边界框效果 2.效果和源码2.1 动态效果2.2 源代码 源码下载 作者:xcLeigh 文章地址:https://blog.csdn.net/weixin_43151418/article/details/143799554 HTML5实现趣味飞船捡金币小游戏(附源码)&…...
Excel表数学于三角函数、统计函数
一、数学与三角函数 函数说明ABS返回数值的绝对值ACOS反余弦函数ACOSH反双曲余弦函数ASIN反正弦函数ASINH反双曲正弦函数ATAN反正切函数ATAN2以 x、y 坐标返回反正切值ATANH反双曲正切函数CEILING向上舍入(指定倍数的整数)COMBIN组合公式COS余弦函数COS…...

小试银河麒麟系统OCR软件
0 前言 今天在国产电脑上办公,需要从一些PDF文件中复制文字内容,但是这些PDF文件是图片转换生成的,不支持文字选择和复制,除了手工输入,我们还可以使用OCR。 1 什么是OCR OCR (Optical Character Recogni…...

Dubbo RPC线程模型
消费端线程模型,提供者端线程模型 消费端线程模型 对 2.7.5 版本之前的 Dubbo 应用,尤其是一些消费端应用,当面临需要消费大量服务且并发数比较大的大流量场景时(典型如网关类场景),经常会出现消费端线程…...

三角波生成函数
% 设置时间范围和采样频率 t 0:0.01:2; % 时间从0到2秒,步长为0.01秒% 定义频率 f 和角频率 theta f 5; % 频率为5Hz theta 2 * pi * f * t;% 初始化输出向量 y zeros(size(t));% 根据给定的公式计算 y for k 1:fy y (-1)^(k-1)*(2 /(k * pi)) * sin(k * the…...
使用Python实现对接Hadoop集群(通过Hive)并提供API接口
安装必要的库 首先,确保已经安装了以下库: pip install flask pip install pyhive代码实现 1. app.py(主应用文件) from flask import Flask, jsonify, request, abort from pyhive import hive import re from datetime impo…...

Qt学习笔记(四)多线程
系列文章目录 Qt开发笔记(一)Qt的基础知识及环境编译(泰山派) Qt学习笔记(二)Qt 信号与槽 Qt学习笔记(三)网络编程 Qt学习笔记(四)多线程 文章目录 系列文章…...

java的小数计算如何保证精度不丢失
前言 学java的肯定都知道,要保证小数运算精度不丢失我们得用BigDecimal对象。这篇文章就分析一下为什么用浮点数会造成精度丢失?BigDecimal是怎么解决精度丢失问题的?下面我们一起看看吧! 浮点数的表示 浮点数在计算机中通常采用 IEEE 75…...
分布式----Ceph应用(下)
目录 创建 Ceph 对象存储系统 RGW 接口 1、对象存储概念 2、创建 RGW 接口 //在管理节点创建一个 RGW 守护进程(生产环境下此进程一般需要高可用,后续介绍) //开启 httphttps ,更改监听端口 //创建 RadosGW 账户 //S3 接口…...
小鹏汽车嵌入式面试题及参考答案
static 变量放在哪个段中? 在 C 和 C++ 等编程语言中,static 变量根据其定义的位置不同放置的段也不同。对于全局的静态变量(在函数体外定义的静态变量),它会被放在数据段(.data 段或者.bss 段)。如果这个静态变量被初始化了非零值,那么它会被放在.data 段,这个段存储…...

qt5半成品飞机大战小游戏
最近在学Qt,心血来潮做了个飞机大战小游戏,由于一些资源比较难找,就做了个半成品。效果图如下: 目前已做功能:人物飞机的自由移动,子弹的发射,子弹与敌机的物体碰撞,碰撞特效。 缺少功能&#x…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...