力扣题目解析--合并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…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...