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

力扣题目解析--合并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循环来进行链表合并要少很多

逐行解析

  1. 自定义比较器

    struct Compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val; // 最小堆}
    };
    • 这是一个自定义的比较器,用于优先队列中的排序。
    • operator() 定义了比较规则,使得优先队列成为一个最小堆,即队列顶部的节点值是最小的。
  2. 创建优先队列

    priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
    • 使用 priority_queue 创建一个最小堆,存储类型为 ListNode*
    • vector<ListNode*> 是优先队列的底层容器。
    • Compare 是自定义的比较器,确保优先队列按节点值从小到大排序。
  3. 初始化优先队列

    for (auto& list : lists) {if (list) { // 检查链表是否为空pq.push(list);}
    }
    • 遍历输入的链表列表 lists
    • 对于每个链表,检查其是否为空(if (list)),如果不为空,则将其头节点加入优先队列。
  4. 创建虚拟头节点

    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;
    • 创建一个虚拟头节点 dummy,值为 0。
    • current 指向 dummy,用于构建新的链表。
  5. 合并链表

    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 加入优先队列。
  6. 返回新链表的头节点

    return dummy->next;
    • 返回新链表的头节点,即 dummy 的下一个节点。

条件的使用

  • if (list):检查链表是否为空。只有非空链表的头节点才会被加入优先队列。
  • if (top->next):检查当前节点是否有下一个节点。如果有,则将下一个节点加入优先队列,以继续参与后续的合并操作。

 

1. 自定义比较器

什么是比较器?

比较器是一个函数对象,用于定义两个对象之间的比较规则。在 C++ 标准库中,许多容器(如 std::sortstd::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个升序链表

题目 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a;链表数组如下…...

Linux:调试器-gdb/cgdb

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

『VUE』30. 生命周期的介绍(详细图文注释)

目录 生命周期生命周期的8阶段生命周期小例子总结 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 欢迎关注 『VUE』 专栏&#xff0c;持续更新中 生命周期 每个 Vue 组件实例在创建时都需要经历一系列的初始化步骤&#xff0c;比如设置好数据侦听&#xff0c;编译模板&#xf…...

Python 人脸检测:使用 Dlib 和 OpenCV

简介 本文用Python、Dlib 和 OpenCV 库来检测图像中的人脸&#xff0c;并在人脸上绘制矩形框进行窗口显示。 环境准备 在开始之前&#xff0c;请确保您的计算机上已安装 Python。此外&#xff0c;您还需要安装以下库&#xff1a; dlib&#xff1a;一个包含多种机器学习算法…...

【大数据学习 | flume】flume的概述与组件的介绍

1. flume概述 Flume是cloudera(CDH版本的hadoop) 开发的一个分布式、可靠、高可用的海量日志收集系统。它将各个服务器中的数据收集起来并送到指定的地方去&#xff0c;比如说送到HDFS、Hbase&#xff0c;简单来说flume就是收集日志的。 Flume两个版本区别&#xff1a; ​ 1&…...

torch.is_storage()

torch.is_storage() 判断给定的对象是否是一个 PyTorch 存储对象 PyTorch 存储对象&#xff1a;PyTorch 中&#xff0c;存储对象&#xff08;Storage&#xff09;是一个低级别的对象&#xff0c;它表示一个存储数据的连续内存块。存储对象不包含任何关于数据如何解释的信息&a…...

2411rust,编译时自动检查配置

原文 Cargo和编译器团队很高兴地宣布,从Rust1.80(或nightly-2024-05-05)开始,会自动检查每个可访问的#[cfg],看看是否与期望的配置名和值匹配. 这帮助验证crate,是否正确处理不同目标平台或函数的条件编译.它确保在期望和使用设置的配置间保持一致,帮助在开发过程的早期抓住潜…...

在 Ubuntu 中用 VSCode 配置 C 语言项目的编译与调试(详解教程)

目录 一、准备工作二、配置 VSCode 的编译任务三、配置 VSCode 的调试任务四、编译与调试流程五、常见问题排查六、总结 在 C 语言开发过程中&#xff0c;调试与编译是不可缺少的环节&#xff0c;而 VSCode&#xff08;Visual Studio Code&#xff09;作为一个强大且轻量级的编…...

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 源代码 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/143799554 HTML5实现趣味飞船捡金币小游戏(附源码)&…...

Excel表数学于三角函数、统计函数

一、数学与三角函数 函数说明ABS返回数值的绝对值ACOS反余弦函数ACOSH反双曲余弦函数ASIN反正弦函数ASINH反双曲正弦函数ATAN反正切函数ATAN2以 x、y 坐标返回反正切值ATANH反双曲正切函数CEILING向上舍入&#xff08;指定倍数的整数&#xff09;COMBIN组合公式COS余弦函数COS…...

小试银河麒麟系统OCR软件

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

Dubbo RPC线程模型

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

三角波生成函数

% 设置时间范围和采样频率 t 0:0.01:2; % 时间从0到2秒&#xff0c;步长为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接口

安装必要的库 首先&#xff0c;确保已经安装了以下库&#xff1a; pip install flask pip install pyhive代码实现 1. app.py&#xff08;主应用文件&#xff09; from flask import Flask, jsonify, request, abort from pyhive import hive import re from datetime impo…...

Qt学习笔记(四)多线程

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

java的小数计算如何保证精度不丢失

前言 学java的肯定都知道&#xff0c;要保证小数运算精度不丢失我们得用BigDecimal对象。这篇文章就分析一下为什么用浮点数会造成精度丢失&#xff1f;BigDecimal是怎么解决精度丢失问题的?下面我们一起看看吧&#xff01; 浮点数的表示 浮点数在计算机中通常采用 IEEE 75…...

分布式----Ceph应用(下)

目录 创建 Ceph 对象存储系统 RGW 接口 1、对象存储概念 2、创建 RGW 接口 //在管理节点创建一个 RGW 守护进程&#xff08;生产环境下此进程一般需要高可用&#xff0c;后续介绍&#xff09; //开启 httphttps &#xff0c;更改监听端口 //创建 RadosGW 账户 //S3 接口…...

小鹏汽车嵌入式面试题及参考答案

static 变量放在哪个段中? 在 C 和 C++ 等编程语言中,static 变量根据其定义的位置不同放置的段也不同。对于全局的静态变量(在函数体外定义的静态变量),它会被放在数据段(.data 段或者.bss 段)。如果这个静态变量被初始化了非零值,那么它会被放在.data 段,这个段存储…...

qt5半成品飞机大战小游戏

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

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

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开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

网站指纹识别

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

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 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、…...