当前位置: 首页 > 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…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...