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

【LeetCode每日一题】——LCR 078.合并 K 个升序链表

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目注意】
  • 六【题目示例】
  • 七【题目提示】
  • 八【解题思路】
  • 九【时间频度】
  • 十【代码实现】
  • 十一【提交结果】

一【题目类别】

  • 优先队列

二【题目难度】

  • 困难

三【题目编号】

  • LCR 078.合并 K 个升序链表

四【题目描述】

  • 给定一个链表数组,每个链表都已经按升序排列。
  • 请将所有链表合并到一个升序链表中,返回合并后的链表。

五【题目注意】

  • 本题与主站 23 题相同: https://leetcode-cn.com/problems/merge-k-sorted-lists/

六【题目示例】

  • 示例 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

八【解题思路】

  • 使用优先队列(小顶堆)解决该问题
  • 小顶堆维护各个链表没有被合并的的节点的最前面的节点
  • 这样我们每次都会取出所有链表中值最小的节点
  • 然后依次将所有节点存入小顶堆中再将其合并为一个链表
  • 最后返回结果即可

九【时间频度】

  • 时间复杂度: O ( k n × l o g k ) O(kn × logk) O(kn×logk) k k k为优先队列中的元素个数, n n n为传入的链表个数
  • 空间复杂度: O ( k ) O(k) O(k) k k k为优先队列中的元素个数

十【代码实现】

  1. Java语言版
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 定义一个类 Status,用来存储链表节点值和对应的节点指针class Status implements Comparable<Status> {int val;ListNode node;// 构造函数,初始化节点值和指针Status(int val, ListNode node) {this.val = val;this.node = node;}// 实现 Comparable 接口,按照节点值从小到大排序public int compareTo(Status status) {return this.val - status.val;}}// 合并多个有序链表public ListNode mergeKLists(ListNode[] lists) {// 定义一个优先队列(小顶堆),会根据 Status 类中的节点值进行排序PriorityQueue<Status> pQueue = new PriorityQueue<Status>();// 遍历所有链表,把每个链表的第一个节点放入优先队列for (ListNode node : lists) {if (node != null) {pQueue.offer(new Status(node.val, node));}}// 创建一个虚拟头节点和尾节点,方便构建结果链表ListNode head = new ListNode(0);ListNode tail = head;// 循环处理优先队列中的节点,直到队列为空while (!pQueue.isEmpty()) {Status min_node = pQueue.poll();tail.next = min_node.node;tail = tail.next;if (min_node.node.next != null) {pQueue.offer(new Status(min_node.node.next.val, min_node.node.next));}}// 返回合并后的链表(哑节点的下一个节点)return head.next;}
}
  1. Python语言版
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextimport heapqclass Solution:# 定义一个类 Status,用来存储链表节点值和对应的节点指针class Status:# 构造函数,初始化节点值和指针def __init__(self, val, node):self.val = valself.node = node# 实现接口,按照节点值从小到大排序def __lt__(self, other):return self.val < other.val# 合并多个有序链表def mergeKLists(self, lists: List[ListNode]) -> ListNode:# 定义一个优先队列(小顶堆),会根据 Status 类中的节点值进行排序pQueue = []# 遍历所有链表,把每个链表的第一个节点放入优先队列for node in lists:if node is not None:heapq.heappush(pQueue, self.Status(node.val, node))# 创建一个虚拟头节点和尾节点,方便构建结果链表head = ListNode(0)tail = head# 循环处理优先队列中的节点,直到队列为空while pQueue:min_node = heapq.heappop(pQueue)tail.next = min_node.nodetail = tail.nextif min_node.node.next is not None:heapq.heappush(pQueue, self.Status(min_node.node.next.val, min_node.node.next))# 返回合并后的链表(哑节点的下一个节点)return head.next
  1. C++语言版
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Status {public:int val;ListNode* node;Status(int v, ListNode* n) : val(v), node(n) {}bool operator<(const Status& other) const {return val > other.val;}
};class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {std::priority_queue<Status> pQueue;for (ListNode* node : lists) {if (node != nullptr) {pQueue.push(Status(node->val, node));}}ListNode* head = new ListNode(0);ListNode* tail = head;while (!pQueue.empty()) {Status min_node = pQueue.top();pQueue.pop();tail->next = min_node.node;tail = tail->next;if (min_node.node->next != nullptr) {pQueue.push(Status(min_node.node->next->val, min_node.node->next));}}ListNode* result = head->next;delete head;return result;}
};

十一【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. Python语言版
    在这里插入图片描述

  3. C++语言版
    在这里插入图片描述

相关文章:

【LeetCode每日一题】——LCR 078.合并 K 个升序链表

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目注意】六【题目示例】七【题目提示】八【解题思路】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】 优先队列 二【题目难度】 困难 三【题目编号】 LCR 078.合并 K 个升序链表 …...

代码随想录算法训练营第五十九天 | dijkstra(堆优化版)精讲

目录 dijkstra&#xff08;堆优化版&#xff09;精讲 思路 堆优化细节 方法一&#xff1a; 最小堆优化 dijkstra&#xff08;堆优化版&#xff09;精讲 题目链接&#xff1a;卡码网&#xff1a;47. 参加科学大会 文章讲解&#xff1a;代码随想录 小明是一位科学家&#x…...

go语言后端开发学习(七)——如何在gin框架中集成限流中间件

一.什么是限流 限流又称为流量控制&#xff08;流控&#xff09;&#xff0c;通常是指限制到达系统的并发请求数。 我们生活中也会经常遇到限流的场景&#xff0c;比如&#xff1a;某景区限制每日进入景区的游客数量为8万人&#xff1b;沙河地铁站早高峰通过站外排队逐一放行的…...

SpringBoot2:web开发常用功能实现及原理解析-整合EasyExcel实现Excel导入导出功能

1、工程包结构 主要是这5个Java类 2、导入EasyExcel包 这里同时贴出其他相关springboot的基础包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId></dependency><depend…...

CTFShow-信息搜集

Web1&#xff1a; ​ 题目描述&#xff1a;开发注释未及时删除 。 ​ 打开题目后提示web1:where is flag? ​ ctrlu读取源码。 Web2&#xff1a; ​ 题目描述&#xff1a;js前台拦截 无效操作 ​ 打开题目后显示&#xff1a;无法查看源代码 ​ 右键无法用&#xff0c;…...

Facebook的虚拟现实功能简介:社交网络的新前沿

在科技飞速发展的今天&#xff0c;虚拟现实&#xff08;VR&#xff09;已经从科幻小说中的梦想变成了触手可及的现实。作为全球领先的社交平台&#xff0c;Facebook&#xff08;现已更名为Meta&#xff09;正大力推动虚拟现实技术的发展&#xff0c;以重新定义用户的社交体验。…...

Redis embstr 编码

embstr 编码 是 Redis 中一种优化存储小型字符串的编码方式。它是 Redis 内部存储字符串的多种方式之一&#xff0c;特别适用于存储长度不超过 44 字节的小字符串。...

【Elasticsearch系列二】安装 Kibana

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

中国电子学会202403青少年软件编程(Python)等级考试试卷(三级)真题与解析

202403Python 三级真题 一、选择题 1.在 Python 中,hex(2023)的功能是?( ) A.将十进制数 2023 转化为十六进制数 B.将十进制数 2023 转化为八进制数 C.将十六进制数 2023 转化为十进制数 D.将八进制数 2023 转化为十进制数 2.下列表达式的值与其他三个选项不相…...

k8s 资源管理

文章目录 ResourceQuota什么是资源配额定义一个ResourceQuotaResourceQuota的使用 LimitRangeLimitRange的用途示例1&#xff1a;配置默认的requests和limits示例2&#xff1a;配置requests和limits的范围 QoS什么是服务质量保证示例1&#xff1a;实现QoS为Guaranteed的Pod示例…...

演示:基于WPF的自绘的中国地铁轨道控件

一、目的&#xff1a;演示一个基于WPF的自绘的中国地铁轨道控件 二、效果演示 北京地铁 成都地铁 上海地铁 深圳地铁 南京地铁 长春地铁 哈尔滨地铁 武汉地铁 厦门地铁 香港地铁 三、功能 支持平移、缩放等操作 鼠标悬停显示线路信息和站点信息 按表格显示&#xff0c;按纸张…...

设计模式(Design Patterns)

设计模式&#xff08;Design Patterns&#xff09;是软件开发人员在软件设计过程中面临的一般性问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。设计模式的目的是为了提高代码的可重用性、可维护性、可读性、可靠性以及灵活性。设…...

C++:opencv生成结构元素用于膨胀腐蚀等cv::getStructuringElement

cv::getStructuringElement 是 OpenCV 库中用于生成结构元素的函数。结构元素在形态学操作中&#xff08;如膨胀、腐蚀、开运算、闭运算等&#xff09;扮演着关键角色。这个函数可以创建不同形状和尺寸的结构元素&#xff0c;以适应不同的图像处理需求。 函数原型 cv::Mat cv…...

最大余额法,解决百分比计算相加不等于100%(扇形/饼图百分比使用的此算法)

在开发项目的过程中有时候需要进行计算百分比&#xff0c;例如计算饼状图百分比。有时候在计算的过程中常规四舍五入计算会发生所有计算的值相加不等于100%的情况 这是 get_percent_value 函数的 JavaScript 版本&#xff1a; /*** 最大余额法&#xff0c;解决百分比计算相加不…...

哈希表简单介绍

概念 在顺序结构以及平衡树中&#xff0c;元素关键字与他们存储的位置并没有直接的映射关系&#xff0c;从而会影响查找关键字的效率&#xff0c;顺序结构中查找关键字的时间复杂度为O&#xff08;N&#xff09;&#xff0c;平衡树查找关键字的时间复杂度为O&#xff08;log2^…...

kafka 之 本地部署单机版

安装JDK 查看你选择的版本需要安装哪一个版本的jdk 网址 下载 JDK下载 注&#xff1a;如果网页不允许下载&#xff0c;使用wget命令下载即可&#xff0c;下载之后安装。 建议使用rpm安装&#xff0c;之后使用 update-alternatives --config java 控制当前环境使用Java的版…...

开发一款通过蓝牙连接控制水电表的微信小程序

增强软硬件交互 为了更好的解决师生生活中的实际问题&#xff0c;开发蓝牙小程序加强了和校区硬件的交互。 比如通过蓝牙连接控制水电表&#xff0c;减少实体卡片的使用。添加人脸活体检测功能&#xff0c;提高本人认证效率&#xff0c;减少师生等待时间。 蓝牙水电控展示 蓝…...

力扣14.最长公共前缀

思路&#xff1a;将字符串数组中第一个字符串用作参考&#xff1b; 8.将他的长度作为范围&#xff0c;因为超范围了之后就不会再有公共前缀了 9.将字符串数组的长度也作为范围&#xff0c;意思是便利字符串数组中的字符串 11.开始第一层循环&#xff0c;依次遍历第一个字符串的…...

你也喜欢“钓鱼“吗?

免责声明:本文仅做分享! 目录 什么是网络钓鱼 流程 攻击手法 0-隐藏自己 1-office宏 创建xxx.dotm 创建xxx.docx 2-RLO 自解压 3-快捷方式lnk 4-邮件伪造 Swaks Gophish 5-网站克隆 setoolkit nginx反向代理 前端页面克隆 6-wifi钓鱼 7-其他 防御 溯源 反…...

druid jdbc 执行 sql 输出 开销耗时

druid 执行sql输出 参考链接配置_LogFilter alibaba/druid Wiki GitHub 看不太懂的往这里瞅瞅。 1. 别名映射 这个地方 给我们提供了 5 种 logfilter : log4j、log4j2、slf4j、commonlogging和commonLogging 每一种实际上都代表一个日志框架 或 日志门面。 -Ddruid.fil…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...