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

LeetCode--23. 合并 K 个升序链表【堆和分治】

23. 合并 K 个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。


正文

这道题有多种解决方案

比较容易,又比较直观的就是堆排序,将每个节点加入最小根堆中,依次弹出加入最后的链表,就可得出答案,事实上,并不需要每次都将所有链表加入,只需要最开始将每个链表的头节点加入,然后在弹出链表时,直接将弹出的节点的下一个节点再加入堆即可,这样能够有效节省空间。

代码如下:

func mergeKLists(lists []*ListNode) *ListNode {lh := &ListHeap{}heap.Init(lh)for _, node := range lists {if node != nil {heap.Push(lh, node)}}dummy := &ListNode{}tmp := dummyfor lh.Len() > 0 {Node := heap.Pop(lh).(*ListNode)tmp.Next = Nodetmp = tmp.Nextif Node.Next != nil {heap.Push(lh, Node.Next)}}return dummy.Next
}type ListHeap []*ListNodefunc (l *ListHeap) Len() int {return len(*l)
}func (l *ListHeap) Less(i, j int) bool {return (*l)[i].Val < (*l)[j].Val
}func (l *ListHeap) Swap(i, j int) {(*l)[i], (*l)[j] = (*l)[j], (*l)[i]
}func (l *ListHeap) Push(x any) {*l = append(*l, x.(*ListNode))
}func (l *ListHeap) Pop() any {res := (*l)[len(*l)-1]*l = (*l)[:len(*l)-1]return res
}

堆排序不用ide也太难写了~

分治

跟归并排序的思路类似,将链表切片分成两部分,分别合并成一个链表,再将这两个链表进行合并。

可以理解为:

	链表1  链表2    链表3    链表4|		  |		|		  ||		  |		|		  ||		  |		|		  ||		  |		|		  |+————+————+     +————+————+|			 	 |链表			链表+————————+——————+||最终链表

代码如下:

func mergeKLists(lists []*ListNode) *ListNode {return Merge(lists, 0, len(lists) - 1)
}func Merge(lists []*ListNode, l int, r int) *ListNode {if l == r {return lists[l]} else if l > r {return nil}mid := (l + r) / 2return MergeTwoLists(Merge(lists, l, mid), Merge(lists, mid + 1, r))
}func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {dummy := &ListNode{}tmp := dummyfor list1 != nil && list2 != nil {if list1.Val > list2.Val {tmp.Next = list2tmp = tmp.Nextlist2 = list2.Next} else {tmp.Next = list1tmp = tmp.Nextlist1 = list1.Next}}if list1 != nil {tmp.Next = list1}if list2 != nil {tmp.Next = list2}return dummy.Next
}

相关文章:

LeetCode--23. 合并 K 个升序链表【堆和分治】

23. 合并 K 个升序链表 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 正文 这道题有多种解决方案 堆 比较容易&#xff0c;又比较直观的就是堆排序&#xff0c;将每个节点加入最小根堆中&…...

tp6上传文件大小超过了最大值+验证文件上传大小和格式函数

问题&#xff1a; 最近用tp6的文件上传方法上传文件时报文件过大错误。如下所示&#xff1a; $file $this->request->file(file);{"code": 1,"msg": "上传文件大小超过了最大值&#xff01;","data": {"code": 1,&q…...

解决 Mac 只显示文件大小,不显示目录大小

前言 在使用 mac 的时候总是只显示文件的大小&#xff0c;不显示文件夹的大小&#xff0c;为了解决问题可以开启“计算文件夹”。 步骤 1.进入访达 2.工具栏点击“显示”选项&#xff0c;点击 “查看显示选项” 3.勾选 显示“资源库"文件夹 和 计算所有大小 或者点击…...

分布式大语言模型服务引擎vLLM论文解读

论文地址&#xff1a;Efficient Memory Management for Large Language Model Serving with PagedAttention 摘要 大语言模型&#xff08;LLMs&#xff09;的高吞吐量服务需要一次对足够多的请求进行批处理。然而&#xff0c;现有系统面临困境&#xff0c;因为每个请求的键值…...

快速入门——Vue框架快速上手

学习自哔哩哔哩上的“刘老师教编程”&#xff0c;具体学习的网站为&#xff1a;8.Vue框架快速上手_哔哩哔哩_bilibili&#xff0c;以下是看课后做的笔记&#xff0c;仅供参考。 第一节&#xff1a;前端环境准备 编码工具VSCode【www.code.visualstudio.com】/WebStorm也可&am…...

机器学习,我们主要学习什么?

机器学习的发展历程 机器学习的发展历程&#xff0c;大致分为以下几个阶段&#xff1a; 1. 起源与早期探索&#xff08;20世纪40年代-60年代&#xff09; 1949年&#xff1a;Hebb提出了基于神经心理学的学习机制&#xff0c;开启了机器学习的先河1950年代&#xff1a;机器学习的…...

安卓burp抓包,bypass ssl pinning

好久好久没有发东西了。主要是懒。。。 这几天在搞apk渗透&#xff0c;遇到了burp无法抓包问题&#xff0c;觉得可以写下来。 问题描述 1. 一台安卓手机&#xff0c;装了面具&#xff0c;可以拿到root 2. 电脑上有burp&#xff0c;设置代理 3.手机和电脑连同一个网段&…...

【如何基于Debian构建Kali Linux】

如何基于Debian构建Kali Linux 修改apt源获取Kali的apt密钥更新并安装Kali Linux软件包添加非root用户 在Linux系统的应用领域中&#xff0c;Kali Linux因其在渗透测试、安全审计等方面的出色表现而备受关注。Kali Linux是一个基于Debian的Linux发行版。接下来&#xff0c;将介…...

Hopper架构 GEMM教程

一 使用 1.1 makefile compile:nvcc -arch=sm_90a -lcuda -lcublas -std=c++17 matmul_h100_optimal.cu -o testrun:./test加入-lcublas,不然会有函数无法被识别 二 代码分析 2.1 kernel外参数分析 2.1.1 基本参数 constexpr int BM = 64*2;constexpr int BN = 256;cons…...

CV -- 基于GPU版CUDA环境+Pycharm YOLOv8 目标检测

目录 下载 CUDA 下载 cuDNN 下载 anaconda 安装 PyTorch pycharm 搭配 yolo 环境并运行 阅读本文须知&#xff0c;需要电脑中有 Nvidia 显卡 下载 CUDA 打开 cmd &#xff0c;输入 nvidia-smi &#xff0c;查看电脑支持 CUDA 版本&#xff1a; 我这里是12.0&#xff0c;进入…...

ELK8.17部署(Ubantu24x64)

检查java环境 ELK8.x不支持java8 若无环境可执行 sudo apt install openjdk-17-jre-headless 准备安装包 官网下载地址: ELK products 搜Elasticsearch、Kibana、Logstash、Filebeat versions需一致&#xff0c;这里使用8.17.0 Elasticsearch Kibana Logstash Filebeat e…...

Python glob模块使用示例代码

Python 的 glob 模块位于标准库中,专门用于在文件系统中进行 文件路径模式匹配(与 Shell 中的通配符匹配类似)。它可以根据 通配符(如 *、? 和 [])来查找符合条件的文件路径。 1. glob 模块的核心功能 路径模式匹配:根据指定的通配符模式,匹配对应的文件路径。递归搜索…...

npm、pnpm和yarn有什么区别

1. 性能和速度 npm&#xff1a;在较早的版本中&#xff0c;速度较慢&#xff0c;尤其是在安装大型依赖集时。自npm 5以后的版本引入了缓存机制&#xff0c;性能有所提升。yarn&#xff1a;由Facebook开发&#xff0c;主要目标是提高安装速度。使用了缓存和并行安装&#xff08;…...

Java 基础面试

final、finalize 和 finally 的不同之处&#xff1f; Final&#xff1a;是一个修饰符&#xff0c;可以修饰变量、方法和类。如果 final 修饰变量&#xff0c;意味着该变量的值在初始化后不 能被改变。Finalize&#xff1a;方法是在对象被回收之前调用的方法&#xff0c; 给对象…...

ac的dhcp池里option43配错导致ap无法上线问题排查过程

dhcp池里ac地址配错&#xff0c;导致ap无法上线问题排查过程 问题&#xff1a;ap手动设置ac的ip正常注册在线&#xff0c;但dhcp获得ip和ac地址发现无法在ac上注册成功。 组网&#xff1a; ac旁路结构&#xff0c;路由器lan口地址172.16.1.1&#xff0c;开dhcp服务&#xff0…...

第1章:LangChain4j的聊天与语言模型

LangChain4J官方文档翻译与解析 目标文档路径: https://docs.langchain4j.dev/tutorials/chat-and-language-models/ 语言模型的两种API类型 LangChain4j支持两种语言模型&#xff08;LLM&#xff09;的API&#xff1a; LanguageModel&#xff1a;这种API非常简单&#xff0c;…...

Cython学习笔记1:利用Cython加速Python运行速度

Cython学习笔记1&#xff1a;利用Cython加速Python运行速度 CythonCython 的核心特点&#xff1a;利用Cython加速Python运行速度1. Cython加速Python运行速度原理2. 不使用Cython3. 使用Cython加速&#xff08;1&#xff09;使用pip安装 cython 和 setuptools 库&#xff08;2&…...

【从0做项目】Java音缘心动(1)———项目介绍设计

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 零&#xff1a;项目结果展示 一&#xff1a;音乐播放器Web网页介绍 二&#xff1a;前期准备工作&…...

智慧农业新生态 | 农业数字化服务平台——让土地生金,让服务无忧

一部手机管农事&#xff0c;从播种到丰收&#xff0c;全链路数字化赋能&#xff01; 面向农户、农机手、农服商、农资商打造的一站式农业产业互联网平台&#xff0c;打通农资交易、农机调度、农服管理、技术指导全场景闭环&#xff0c;助力乡村振兴提效增收。 三大核心场景&am…...

C++编程,#include <iostream>详解,以及using namespace std;作用

在C编程中&#xff0c;#include <iostream> 是用来包含输入/输出流头文件的预处理指令。它允许程序使用标准的输入/输出对象如 std::cout 和 std::cin&#xff0c;以便与标准输入和输出流进行交互。这一头文件是编写输入输出操作时必不可少的部分。 讲到这里&#xff0c…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...