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.最长递增子序列 题目描述 给你一个整数…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...