LeetCode23.合并K个升序链表
题目
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 :
输入: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
思路
要将多个已按升序排列的链表合并成一个升序链表,可以使用分治法的思想。我们利用分治法的思想,递归地将链表数组拆分成两部分,然后合并这些部分,最终得到一个合并后的升序链表。
-
定义一个辅助函数mergeTwoLists(ListNode* list1, ListNode* list2),用于合并两个链表的方法,这是我们之前讨论过的合并两个升序链表的方法。
-
在mergeKLists函数中,首先判断输入的链表数组是否为空,如果为空则返回nullptr。
-
利用分治法的思想,将链表数组不断地拆分成两部分,然后递归地合并这些部分,直到只剩下一个链表为止。具体步骤如下:
- 计算链表数组的中间位置mid,将链表数组拆分成两部分:左半部分为[0, mid-1],右半部分为[mid, size-1]。
- 递归调用mergeKLists函数,分别对左右两部分进行合并,得到leftList和rightList。
- 最终,再调用mergeTwoLists方法将leftList和rightList合并为一个新的升序链表,并返回合并后的结果。
-
最终返回合并后的链表即可。
Code:
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if (lists.empty()) {return nullptr;}return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left == right) {return lists[left];}if (left < right) {int mid = left + (right - left) / 2;ListNode* leftList = merge(lists, left, mid);ListNode* rightList = merge(lists, mid + 1, right);return mergeTwoLists(leftList, rightList);}return nullptr;}ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) {return list2;}if (!list2) {return list1;}if (list1->val < list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};
相关文章:
LeetCode23.合并K个升序链表
题目 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 : 输入:lists [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下&…...

(01)Hive的相关概念——架构、数据存储、读写文件机制
目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型(Data Model) 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …...

二维码扫码登录原理,其实比你想的要简单的多
二维码,大家再熟悉不过了 购物扫个码,吃饭扫个码,坐公交也扫个码 在扫码的过程中,大家可能会有疑问:这二维码安全吗? 会不会泄漏我的个人信息? 更深度的用户还会考虑:我的系统是不…...
Java 实现 Awaitable(多线程并行等待,类似 AutoEventReset 的作用)
AutoEventReset、ManualEventReset,是我们在多线程并行编程之中常常需要涉及的,但是 ManualEventReset 可能用的并没有那么多,这个多用于实现读写锁的,当然 Java 自己库提供了官方实现,就没必要自己去整了。 C/C 里面…...

AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略
AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读:Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…...
IListManger feeds流
目的:将feeds的分页加载和下拉刷新,与网络请求关联起来 ListLibRecyclerViewProxy 在this.getRecyclerView().addOnScrollListener中记录事件 recyclerView.computeVerticalScrollOffset() // 已经向下滚动的距离,为0时表示已处于顶部。 recyclerView.computeVerticalScro…...

视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?
视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体,可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务,在应用场景上,平台可以运用在互联网教育、在线课堂、游戏…...

设计模式三:工厂模式
工厂模式包括简单工厂模式、工厂方法模式和抽象工厂模式,其中后两者属于23中设计模式 各种模式中共同用到的实体对象类: //汽车类:宝马X3/X5/X7;发动机类:B48TU、B48//宝马汽车接口 public interface BMWCar {void s…...

2024.2.15 模拟实现 RabbitMQ —— 消息持久化
目录 引言 约定存储方式 消息序列化 重点理解 针对 MessageFileManager 单元测试 小结 统一硬盘操作 引言 问题: 关于 Message(消息)为啥在硬盘上存储? 回答: 消息操作并不涉及到复杂的增删查改消…...

【技巧】金融企业在搭建服务器时,选择私有云方案还是全栈专属云?
金融企业在搭建服务器时,选择私有云方案还是全栈专属云,需要根据企业的具体需求和情况进行综合考虑。Cloud Ace云一作为谷歌云全球战略合作伙伴,专注于企业级出海云服务 ,为大家带来两种方案的优劣势比较: 私有云 优势…...
【大厂AI课学习笔记】【2.2机器学习开发任务实例】(10)模型评测
目录 一、模型评测的定义 二、模型评测的方法 三、模型评测的原理 四、涉及的关键技术 五、实例阐述 今天是2.2机器学习开发任务实例的最后一个部分——模型评测。 不同的模型计算出的MSE值会有差异,通过模型的选择,参数的变换,可以比较…...

【C++游戏开发-03】贪吃蛇
文章目录 前言一、工具准备1.1游戏开发框架1.2visual studio2022下载1.3easyX下载1.4图片素材 二、逻辑分析2.1数据结构2.2蛇的移动2.3吃食物2.4游戏失败 三、DEMO代码实现四、完整源代码总结 🐱🚀个人博客https://blog.csdn.net/qq_51000584?typeblo…...

如何理解CSS的边框宽度?
CSS 边框宽度学习手记 CSS 边框宽度小概念 在CSS的世界里,border-width这个属性真的很实用,它能帮我指定HTML元素四周边框的宽度。这个宽度嘛,可以用像素px、点pt、厘米cm、相对单位em这些来表示,很方便吧!还有呢&am…...
java 写入写出 zip
package com.su.test.aaaTest.ioTest; import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.IOException; import java.util.zip.ZipEntry; import java.util.zip.ZipOutputStream; /** 将文件压缩到 zip 中 */ public c…...

问题解决:‘telnet‘ 不是内部或外部命令,也不是可运行的程序 或批处理文件
当在windows终端中运行telnet指令的时候,发现指令不可用,原因在于系统没安装telnet功能。 解决方法: 打开控制面板–》程序–》启用或关闭windows功能–》勾选Telnet客户端,点击确定即可。...
从基础到高级:Linux用户与用户组权限设置详解
目录 博客前言: 一.简介 1.用户的定义 用户账户分类 2.用户组的定义 二.用户的相关linux语法 1.创建用户(useradd) 2.删除用户(userdel) 3.修改用户(usermod) 4.修改用户密码 5.su切…...
【感知机】感知机(perceptron)学习算法知识点汇总
机器学习——感知机 感知机(perceptron)是一种二分类的线性模型,属于判别模型,也称为线性二分类器。输入为实例的特征向量,输出为实例的类别(取1和-1)。可以视为一种使用阶梯函数激活的人工神经元,例如通过梅尔频率倒谱系数(MFCC…...

蓝桥杯:C++二分算法
在基本算法中,二分法的应用非常广泛,它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。 二分法有整数二分和实数二分两种应用场景 二分法的概念 二分法的概念很简单,每次把搜索范围缩小为上一…...

Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素
思路:链表相关的问题建议就是画图去解决,虽然理解起来很容易,但就是写代码写不出来有时候,依次去遍历第二节点如果与前一个节点相等则跳过,不相等则遍历第三个节点 /*** Definition for singly-linked list.* struct …...
@ 代码随想录算法训练营第8周(C语言)|Day56(动态规划)
代码随想录算法训练营第8周(C语言)|Day56(动态规划) Day56、动态规划(包含题目 ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组 ) 300.最长递增子序列 题目描述 给你一个整数…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...