当前位置: 首页 > 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.最长递增子序列 题目描述 给你一个整数…...

面试复盘(Debrief)的艺术:挂了面试不可怕,如何通过感谢信获取真实Feedback并为下次“埋伏笔”?

在2026年竞争极其激烈的北美科技求职市场中&#xff0c;即使是背景最优秀的候选人&#xff0c;也必然会经历面试失败。在工业界的招聘漏斗中&#xff0c;由于技术栈匹配度、团队预算&#xff08;Headcount&#xff09;变动或单纯的竞争者过强&#xff0c;收到拒信&#xff08;R…...

滑动窗口-438. 找到字符串中所有字母异位词

文章目录1.题解核心解题思路&#xff08;滑动窗口&#xff09;2.机考代码3.知识点讲解1. map.getOrDefault(key, defaultValue)2. map.put(key, value)3. map.containsKey(key)4. s.toCharArray()5. s.charAt(index)6. Scanner 相关&#xff08;机考必备&#xff09;力扣地址&a…...

属于超级学习者的时代!中国学者用三种策略找到放射组学预测模型的最佳算法

源自风暴统计网&#xff1a;一键统计分析与绘图的网站由于可以使用大量数据进行训练&#xff0c;还能整合基因图谱、影像、脑电图、生理数据等多种数据源&#xff0c;因此机器学习&#xff08;ML&#xff09;算法特别适合个体化医疗。今天分享一篇基于集成机器学习&#xff0c;…...

Legacy-iOS-Kit:让旧设备重获新生的开源解决方案

Legacy-iOS-Kit&#xff1a;让旧设备重获新生的开源解决方案 【免费下载链接】Legacy-iOS-Kit An all-in-one tool to restore/downgrade, save SHSH blobs, jailbreak legacy iOS devices, and more 项目地址: https://gitcode.com/gh_mirrors/le/Legacy-iOS-Kit 当你的…...

3步解决ComfyUI-Florence2视觉语言模型加载失败:实战配置指南

3步解决ComfyUI-Florence2视觉语言模型加载失败&#xff1a;实战配置指南 【免费下载链接】ComfyUI-Florence2 Inference Microsoft Florence2 VLM 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-Florence2 当您在ComfyUI中部署Microsoft Florence2视觉语言模型…...

TFT Overlay:云顶之弈玩家的终极装备合成与羁绊指南

TFT Overlay&#xff1a;云顶之弈玩家的终极装备合成与羁绊指南 【免费下载链接】TFT-Overlay Overlay for Teamfight Tactics 项目地址: https://gitcode.com/gh_mirrors/tf/TFT-Overlay 在云顶之弈的激烈对局中&#xff0c;你是否经常为记不住复杂的装备合成公式而烦恼…...

Qwen3-VL-2B实战:快速搭建一个能“看懂”图片的智能聊天机器人

Qwen3-VL-2B实战&#xff1a;快速搭建一个能"看懂"图片的智能聊天机器人 1. 项目介绍与核心能力 1.1 什么是视觉语言模型 视觉语言模型&#xff08;Vision-Language Model&#xff09;是一种能够同时理解图像和文本的AI技术。不同于传统聊天机器人只能处理文字&am…...

面试官最爱问的哈希表实战:用C++手撕‘存在重复元素II’(附滑动窗口优化思路)

哈希表实战&#xff1a;从暴力解法到最优解法的完整思维路径 在技术面试中&#xff0c;哈希表相关题目几乎是必考内容&#xff0c;而"存在重复元素II"这类问题更是高频出现。这道看似简单的题目背后&#xff0c;隐藏着对候选人算法思维、编码能力和沟通表达的全面考察…...

Tencent Hunyuan3D-1.0模型蒸馏实践:从std版本压缩出移动端可用的轻量模型

Tencent Hunyuan3D-1.0模型蒸馏实践&#xff1a;从std版本压缩出移动端可用的轻量模型 【免费下载链接】Hunyuan3D-1 腾讯开源的Hunyuan3D-1项目&#xff0c;创新提出两阶段3D生成方法&#xff0c;实现快速、高质量的文本到3D和图像到3D转换&#xff0c;融合Hunyuan-DiT模型&am…...

Qwen3.5-9B-AWQ-4bit惊艳效果展示:高清图识+中文摘要真实生成作品集

Qwen3.5-9B-AWQ-4bit惊艳效果展示&#xff1a;高清图识中文摘要真实生成作品集 1. 模型能力概览 Qwen3.5-9B-AWQ-4bit是一款让人眼前一亮的视觉理解模型&#xff0c;它能像人类一样"看懂"图片内容&#xff0c;并用流畅的中文给出专业分析。这个模型特别擅长处理各种…...