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

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个升序链表

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

(01)Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 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 读取文件的过程 …...

二维码扫码登录原理,其实比你想的要简单的多

二维码&#xff0c;大家再熟悉不过了 购物扫个码&#xff0c;吃饭扫个码&#xff0c;坐公交也扫个码 在扫码的过程中&#xff0c;大家可能会有疑问&#xff1a;这二维码安全吗&#xff1f; 会不会泄漏我的个人信息&#xff1f; 更深度的用户还会考虑&#xff1a;我的系统是不…...

Java 实现 Awaitable(多线程并行等待,类似 AutoEventReset 的作用)

AutoEventReset、ManualEventReset&#xff0c;是我们在多线程并行编程之中常常需要涉及的&#xff0c;但是 ManualEventReset 可能用的并没有那么多&#xff0c;这个多用于实现读写锁的&#xff0c;当然 Java 自己库提供了官方实现&#xff0c;就没必要自己去整了。 C/C 里面…...

AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略

AI之Sora&#xff1a;Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读&#xff1a;Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…...

IListManger feeds流

目的:将feeds的分页加载和下拉刷新,与网络请求关联起来 ListLibRecyclerViewProxy 在this.getRecyclerView().addOnScrollListener中记录事件 recyclerView.computeVerticalScrollOffset() // 已经向下滚动的距离,为0时表示已处于顶部。 recyclerView.computeVerticalScro…...

视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?

视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体&#xff0c;可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务&#xff0c;在应用场景上&#xff0c;平台可以运用在互联网教育、在线课堂、游戏…...

设计模式三:工厂模式

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

2024.2.15 模拟实现 RabbitMQ —— 消息持久化

目录 引言 约定存储方式 消息序列化 重点理解 针对 MessageFileManager 单元测试 小结 统一硬盘操作​​​​​​​ 引言 问题&#xff1a; 关于 Message&#xff08;消息&#xff09;为啥在硬盘上存储&#xff1f; 回答&#xff1a; 消息操作并不涉及到复杂的增删查改消…...

【技巧】金融企业在搭建服务器时,选择私有云方案还是全栈专属云?

金融企业在搭建服务器时&#xff0c;选择私有云方案还是全栈专属云&#xff0c;需要根据企业的具体需求和情况进行综合考虑。Cloud Ace云一作为谷歌云全球战略合作伙伴&#xff0c;专注于企业级出海云服务 &#xff0c;为大家带来两种方案的优劣势比较&#xff1a; 私有云 优势…...

【大厂AI课学习笔记】【2.2机器学习开发任务实例】(10)模型评测

目录 一、模型评测的定义 二、模型评测的方法 三、模型评测的原理 四、涉及的关键技术 五、实例阐述 今天是2.2机器学习开发任务实例的最后一个部分——模型评测。 不同的模型计算出的MSE值会有差异&#xff0c;通过模型的选择&#xff0c;参数的变换&#xff0c;可以比较…...

【C++游戏开发-03】贪吃蛇

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

如何理解CSS的边框宽度?

CSS 边框宽度学习手记 CSS 边框宽度小概念 在CSS的世界里&#xff0c;border-width这个属性真的很实用&#xff0c;它能帮我指定HTML元素四周边框的宽度。这个宽度嘛&#xff0c;可以用像素px、点pt、厘米cm、相对单位em这些来表示&#xff0c;很方便吧&#xff01;还有呢&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指令的时候&#xff0c;发现指令不可用&#xff0c;原因在于系统没安装telnet功能。 解决方法&#xff1a; 打开控制面板–》程序–》启用或关闭windows功能–》勾选Telnet客户端&#xff0c;点击确定即可。...

从基础到高级:Linux用户与用户组权限设置详解

目录 博客前言&#xff1a; 一.简介 1.用户的定义 用户账户分类 2.用户组的定义 二.用户的相关linux语法 1.创建用户&#xff08;useradd&#xff09; 2.删除用户&#xff08;userdel&#xff09; 3.修改用户&#xff08;usermod&#xff09; 4.修改用户密码 5.su切…...

【感知机】感知机(perceptron)学习算法知识点汇总

机器学习——感知机 感知机(perceptron)是一种二分类的线性模型&#xff0c;属于判别模型&#xff0c;也称为线性二分类器。输入为实例的特征向量&#xff0c;输出为实例的类别(取1和-1)。可以视为一种使用阶梯函数激活的人工神经元,例如通过梅尔频率倒谱系数&#xff08;MFCC…...

蓝桥杯:C++二分算法

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

Leetcode刷题笔记题解(C++):83. 删除排序链表中的重复元素

思路&#xff1a;链表相关的问题建议就是画图去解决&#xff0c;虽然理解起来很容易&#xff0c;但就是写代码写不出来有时候&#xff0c;依次去遍历第二节点如果与前一个节点相等则跳过&#xff0c;不相等则遍历第三个节点 /*** Definition for singly-linked list.* struct …...

@ 代码随想录算法训练营第8周(C语言)|Day56(动态规划)

代码随想录算法训练营第8周&#xff08;C语言&#xff09;|Day56&#xff08;动态规划&#xff09; Day56、动态规划&#xff08;包含题目 ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组 &#xff09; 300.最长递增子序列 题目描述 给你一个整数…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...