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

LeetCode热题100(三十四) —— 23.合并K个升序链表

LeetCode热题100(三十四) —— 23.合并K个升序链表

  • 题目描述
  • 代码实现
    • 思路一:选择排序(199ms)
    • 思路二:归并排序(2ms)
  • 思路解析

  • 你好,我是杨十一,一名热爱健身的程序员
  • 在Coding的征程中,不断探索与成长
  • LeetCode热题100——刷题记录(不定期更新)
    此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
    愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我

题目描述

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4

代码实现

思路一:选择排序(199ms)

class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode newHead = new ListNode();ListNode newTail = newHead;while (true) {int index = -1;int minVal = Integer.MAX_VALUE;for (int i = 0; i < lists.length; i++) {if (lists[i] != null && lists[i].val < minVal) {index = i;minVal = lists[i].val;}}if (index == -1) break;newTail .next = lists[index];newTail = newTail .next;lists[index] = lists[index].next;}return newHead.next;}
}

思路二:归并排序(2ms)

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) return null;if (lists.length == 1) return lists[0];int currentLength = lists.length;while (currentLength != 1) {int i = 0;while (i < currentLength / 2) {lists[i] = merge(lists[i * 2], lists[i * 2 + 1]);if (i > 0) {lists[i * 2] = null;lists[i * 2 + 1] = null;}i++;}if (currentLength % 2 == 1) {lists[i] = lists[currentLength - 1];currentLength = currentLength / 2 + 1;} else {currentLength = currentLength / 2;}}return lists[0];}public ListNode merge(ListNode nodeA, ListNode nodeB) {ListNode newHead = new ListNode();ListNode newTail = newHead;while (nodeA != null && nodeB != null) {if (nodeA.val < nodeB.val) {newTail.next = nodeA;nodeA = nodeA.next;} else {newTail.next = nodeB;nodeB = nodeB.next;}newTail = newTail.next;}if (nodeA == null) newTail.next = nodeB;if (nodeB == null) newTail.next = nodeA;return newHead.next;}
}
  • 数据结构
/** 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; }
}

思路解析

  1. 输入:链表头节点的数组ListNode[] lists
  2. 输出:合并后的有序链表头节点ListNode newHead
  3. 思路一:选择排序
    • 遍历所有链表的头节点,将其中最小的添加至有序的newHead链表中
    • 被选中节点的下一个节点作为该链表新的头节点

在这里插入图片描述

  1. 思路二:归并排序
    • 两两链表进行合并,参考LeetCode热题100(二十七)链表 —— 合并两个有序链表
    • 将合并后的结果保存在原数组中,需注意:
      • 合并过程中当链表数量为奇数时,最后单个的链表添加至数组末尾

在这里插入图片描述


  • 你好,我是杨十一,一名热爱健身的程序员
  • 在Coding的征程中,不断探索与成长
  • LeetCode热题100——刷题记录(不定期更新)
    此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
    愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我

相关文章:

LeetCode热题100(三十四) —— 23.合并K个升序链表

LeetCode热题100&#xff08;三十四&#xff09; —— 23.合并K个升序链表 题目描述代码实现思路一&#xff1a;选择排序(199ms)思路二&#xff1a;归并排序(2ms) 思路解析 你好&#xff0c;我是杨十一&#xff0c;一名热爱健身的程序员在Coding的征程中&#xff0c;不断探索与…...

kalilinux - 目录扫描之dirsearch

情景导入 先简单介绍一下dirsearch有啥用。 假如你现在访问一个网站&#xff0c;例如https://www.example.com/ 它是一个电商平台或者其他功能性质的平台。 站在开发者的角度上思考&#xff0c;我们只指导https://www.example.com/ 但不知道它下面有什么文件&#xff0c;文…...

浅谈云计算04 | 云基础设施机制

探秘云基础设施机制&#xff1a;云计算的基石 一、云基础设施 —— 云计算的根基![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/1fb7ff493d3c4a1a87f539742a4f57a5.png)二、核心机制之网络&#xff1a;连接云的桥梁&#xff08;一&#xff09;虚拟网络边界&#xff…...

文件上传 分片上传

分片上传则是将一个大文件分割成多个小块分别上传&#xff0c;最后再由服务器合并成完整的文件。这种做法的好处是可以并行处理多个小文件&#xff0c;提高上传效率&#xff1b;同时&#xff0c;如果某一部分上传失败&#xff0c;只需要重传这一部分&#xff0c;不影响其他部分…...

【0391】Postgres内核 checkpointer process ① 启动初始化

相关文章: 【0108】checkpointer运行原理(概念篇)(1) 【0278】checkpointer 共享内存(CheckpointerShmem)初始化(3) 文章目录 1. 启动 checkpointer process1.1 初始化 checkpointer PID1.2 注册 signal1.3 初始化 last checkpoint time2. 确认 config 的 shared memo…...

链路追踪SkyWalking

链路追踪 链路追踪作用链路追踪的关键概念链路追踪的工作原理常用链路追踪工具链路追踪的实现步骤链路追踪的典型场景 SkyWalkingSkyWalking 的主要功能SkyWalking 的架构安装 SkyWalking从 SkyWalking 的官方 GitHub 仓库 下载最新版本。配置后端存储SkyWalking使用&#xff0…...

Uniapp判断设备是安卓还是 iOS,并调用不同的方法

在 UniApp 中&#xff0c;可以通过 uni.getSystemInfoSync() 方法来获取设备信息&#xff0c;然后根据系统类型判断当前设备是安卓还是 iOS&#xff0c;并调用不同的方法。 示例代码 export default {onLoad() {this.checkPlatform();},methods: {checkPlatform() {// 获取系…...

计算机网络 (42)远程终端协议TELNET

前言 Telnet&#xff08;Telecommunication Network Protocol&#xff09;是一种网络协议&#xff0c;属于TCP/IP协议族&#xff0c;主要用于提供远程登录服务。 一、概述 Telnet协议是一种远程终端协议&#xff0c;它允许用户通过终端仿真器连接到远程主机&#xff0c;并在远程…...

rtthread学习笔记系列-- 23 环形缓冲块 ringblock

文章目录 23 环形缓冲块 ringblock23.1 初始化23.2 PUT & GET 块23.3 块释放23.4 rt_rbb_blk_queue_get23.5 rt_rbb_blk_alloc https://github.com/wdfk-prog/RT-Thread-Study 23 环形缓冲块 ringblock 环形块状缓冲区简称为&#xff1a;rbb。与传统的环形缓冲区不同的是&…...

HunyuanVideo 文生视频模型实践

HunyuanVideo 文生视频模型实践 flyfish 运行 HunyuanVideo 模型使用文本生成视频的推荐配置&#xff08;batch size 1&#xff09;&#xff1a; 模型分辨率(height/width/frame)峰值显存HunyuanVideo720px1280px129f60GHunyuanVideo544px960px129f45G 本项目适用于使用 N…...

Qt——QTableWidget 限制单元格输入范围的方法(正则表达式输入校验法、自定义代理类MyItemDelegrate)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》...

深度学习论文: CAS-ViT: Convolutional Additive Self-attention Vision Transformers

深度学习论文: CAS-ViT: Convolutional Additive Self-attention Vision Transformers for Efficient Mobile Applications CAS-ViT: Convolutional Additive Self-attention Vision Transformers for Efficient Mobile Applications PDF:https://arxiv.org/pdf/2408.03703 PyT…...

PyCharm文档管理

背景&#xff1a;使用PyCharmgit做文档管理 需求&#xff1a;需要PyCharm自动识别docx/xslx/vsdx等文件类型&#xff0c;并在PyCharm内点击文档时唤起系统内关联应用(如word、excel、visio) 设置步骤&#xff1a; 1、file -》 settings -》file types 2、在Files opened i…...

QNAP 上常用的几款软件

当我们谈到 NAS&#xff08;Network Attached Storage&#xff09;时&#xff0c;QNAP 凭借多年的产品迭代、稳定的硬件性能和不断丰富的软件生态&#xff0c;已成为很多家庭及中小型企业的首选。除了存储本身&#xff0c;QNAP 提供的各种官方软件和应用&#xff0c;也为用户带…...

LabVIEW智能水肥一体灌溉控制系统

本文详细介绍了一种基于LabVIEW的智能水肥一体灌溉控制系统的设计与实现。该系统采用模糊控制策略&#xff0c;能够自动调节土壤湿度和肥液浓度&#xff0c;满足不同作物在不同生长阶段的需求&#xff0c;有效提高水肥利用效率&#xff0c;对现代精准农业具有重要的实践和推广价…...

提问:玩游戏输入法总弹出来咋回事哎

玩游戏时输入法总弹出来的问题&#xff0c;通常与电脑的输入法设置、操作系统配置以及游戏程序的兼容性有关。以下是一些常见的解决方法&#xff1a; 一、修改输入法快捷键 禁用不必要的输入法&#xff1a; 在系统的语言设置中&#xff0c;暂时禁用非活动的输入法&#xff0c;…...

链家房价数据爬虫和机器学习数据可视化预测

完整源码项目包获取→点击文章末尾名片&#xff01;...

【微服务】面试题 5、分布式系统理论:CAP 与 BASE 详解

分布式系统理论&#xff1a;CAP 与 BASE 详解 一、CAP 定理 背景与定义&#xff1a;1998 年由加州大学科学家埃里克布鲁尔提出&#xff0c;分布式系统存在一致性&#xff08;Consistency&#xff09;、可用性&#xff08;Availability&#xff09;、分区容错性&#xff08;Part…...

第十二章:算法与程序设计

文章目录&#xff1a; 一&#xff1a;基本概念 1.算法与程序 1.1 算法 1.2 程序 2.编译预处理 3.面向对象技术 4.程序设计方法 5.SOP标志作业流程 6.工具 6.1 自然语言 6.2 流程图 6.3 N/S图 6.4 伪代码 6.5 计算机语言 二&#xff1a;程序设计 基础 1.常数 …...

RAG技术:是将知识库的文档和问题共同输入到LLM中

RAG技术 RAG技术是将知识库的文档和问题共同输入到LLM中 RAG技术是先从知识库中检索出与问题相关的文档片段,然后将这些检索到的文档片段与问题一起输入到LLM中进行回答。具体过程如下: 文本分块 由于LLM的上下文窗口有限,需要将长文本资料分割成较小的块,以便LLM能够有…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

若依登录用户名和密码加密

/*** 获取公钥&#xff1a;前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...