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

使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...