23. 合并K个升序链表

解题思路:两种解法,一种优先级队列,一种分治
优先级队列解法:以节点中存储的值进行排序
依次遍历所有的链表,把链表中的节点加入到优先级队列中
依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到队列为空,
返回新的链表
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((first,second)->first.val-second.val);for (ListNode list : lists) {while (list!=null){queue.add(list);list=list.next;}}ListNode result = new ListNode();ListNode tem = result;while (queue.size()!=0){ListNode node =queue.remove();tem.next =node;tem=tem.next;}tem.next=null;//防止出现循环链,a->b->areturn result.next;}
}分治:类似与归并排序的思想
如果链表的长度大于2:继续对链表进行拆分成两部分,继续使用分治的思想
将链表数组数组分成两半,list[0,left]和list[left,end],分别对这对两部分进行分治排序合并,这两部分排序后的结果first,second
然后对first和second这两个链表进行双链表合并排序,合并思路:双指针:因为两个链表有序,所以只需要依次比较两个元素的大小,然后添加到新的链表中即可
first指针指向第一个链表,second指针指向第二个链表,result保存合并后的链表的头节点的前驱,tail初值指向result
如果fist和second当前指向的节点都不为null,循环遍历:
如果first.val<second.value,tail.next=first,first=first.next,tail=tail.next
否则,tail.next=second,second=second.next,tail=tail.next
循环结束之后,那么first和second只会有一个节点不为null,因为原链表已经有序,所以只需要将不为null的哪个链表添加到prev.next中即可
最终result.next即为合并后链表的第一个节点
如果链表的长度等于1:不需要分治合并,直接返回该链表即可
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {if (lists==null||lists.length==0){return null;}return merge(lists,0,lists.length-1);}//对list[left,right]范围的链表进行合并,返回合并后新的链表public static ListNode merge(ListNode[] lists,int left,int right){if (left==right){return lists[left];}int mid = (left+right)/2;ListNode first = merge(lists,left,mid);//对左半部的链表分进行分治合并,返回合并后的结果ListNode second = merge(lists,mid+1,right);//对右半部分的链表进行分治合并,返回合并后的结果ListNode result = sortMerge(first,second);//对first和second进行双链表合并return result;}public static ListNode sortMerge(ListNode first,ListNode second){ListNode result = new ListNode();ListNode tail = result;while (first!=null&&second!=null){if (first.val<second.val){tail.next= first;first=first.next;}else {tail.next=second;second=second.next;}tail = tail.next;}tail.next=(first==null)?second:first;return result.next;}
}
相关文章:
23. 合并K个升序链表
解题思路:两种解法,一种优先级队列,一种分治优先级队列解法:以节点中存储的值进行排序依次遍历所有的链表,把链表中的节点加入到优先级队列中依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到…...
软中断与tasklet简介
一、软中断 1.1 何为软中断? Linux 系统为了解决中断处理程序执行过长的问题,将中断过程分成了两个阶段,分别是「上半部(Top Half)和下半部分(Bottom Half)」。 上半部用来快速处理中断。一…...
JUC 之 线程阻塞工具 LockSupport
——LockSupport 与 线程中断 线程中断机制 一个线程不应该由其他线程来强制中断或停止,而是应该由线程自己自行停止,所以,Thread.stop,Thread.suspend,Thread.resume 都已经被废弃 在 Java 中没有办法立即停止一条线…...
常用数据结构总结-Java版
常用数据结构总结(Java版) C/Java/Python 数据结构大比较 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Dokzp1HQ-1677329125447)(assets/image-20220116142815859.png)] array 同一种类型数据的集合,其实数组…...
【基础算法】二分例题(我在哪?)
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...
怕上当?来看这份网络钓鱼和诈骗技术趋势
网络钓鱼和诈骗:当前的欺诈类型 网络钓鱼 钓鱼者可以攻击任何在线服务——银行、社交网络、政府门户网站、在线商店、邮件服务、快递公司等——中的证书。但是,顶级品牌的客户往往面临更大风险,因为相比小品牌,人们更喜欢使用和…...
2023年全国最新保安员精选真题及答案6
百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 61.关于保安员职业资格条件说法正确的是()。 A:必须考试合格…...
unity热更新新方案,ILRuntime
ILRuntime 是一个独立的、跨平台的 .NET Runtime,可用于在 Unity 中实现热更功能。使用 ILRuntime,您可以在游戏运行时加载和执行 C# 脚本,而不需要重新编译整个项目。 以下是一些使用 ILRuntime 的基本步骤: 在 Unity Asset St…...
【J1】【队列】报数游戏
题目描述 有 n 个小朋友围成一圈玩游戏,小朋友从 1 至 n 编号,2 号小朋友坐在 1 号小朋友的顺时针方向,3 号小朋友坐在 2 号小朋友的顺时针方向,……,1 号小朋友坐在 n 号小朋友的顺时针方向。 游戏开始,…...
《程序员的自我修养》阅读笔记
文章目录【第2部分】静态链接1 编译过程2 编辑器的工作流程3 链接——模块的拼接4 目标文件目标文件中的段(section)ELF文件结构5 静态链接1 空间与地址分配2 符号解析与重定位【第3部分】装载与动态链接1 装载的方式2 进程的启动3 为什么需要动态链接&a…...
【跟着ChatGPT学深度学习】ChatGPT带我入门深度学习
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...
软工2023个人作业一——阅读和提问
项目内容这个作业属于哪个课程2023年北航敏捷软件工程这个作业的要求在哪里个人作业-阅读和提问我在这个课程的目标是学习并掌握现代软件开发和项目管理技术,体验敏捷开发工作流程这个作业在哪个具体方面帮助我实现目标通读《构建之法》,了解软件工程中基…...
【Redis】线程模型:Redis是单线程还是多线程?
【Redis】线程模型:Redis是单线程还是多线程? 文章目录【Redis】线程模型:Redis是单线程还是多线程?Redis 是单线程吗?Redis 单线程模式是怎样的?Redis 采用单线程为什么还这么快?Redis 6.0 之前…...
FSM(有限状态机)
FSM有限状态机FSM创建控制有限状态机的脚本设置FSM状态机下的各个状态添加测试类FSM的优点FSM 虽然Unity已经有了动画状态机,但是为了代码的开放封闭原则,这时FSM有限状态机的作用就凸显了出来。 创建控制有限状态机的脚本 先创建一个脚本用来控制有限…...
奇妙的background-clip:text
我们在学习CSS3时,一个背景属性background-clip用来对背景进行裁剪,即指定背景绘制的区域,通常我们使用的几个属性如下:值说明border-box默认值。背景绘制在边框方框内(剪切成边框方框)。padding-box背景绘…...
Vmware虚拟机无法联通主机解决方法二
昨天在遇到了VMware 虚拟机无法联通主机,导致我在CentOS-7 搭建的伪Hadoop3 服务,无法访问管理平台,使用将网络编辑器修改为“桥接”模式解决。今天在学习HBase 时,昨天的问题又重新了,我通过SSH 工具MobaXterm 都无法…...
Boost资料整理备忘
Boost资料整理备忘 网络资源 书籍: The Boost C Libraries官方文档 Boost Library Documentation random boost.randomBoost随机库的简单使用:Boost.Random(STL通用)tutorialstd::random boost::asio Boost.Asio 网络编程 - 基本原理Boost.Asio DocBoost定时器 网…...
规则引擎与风控系统01:新问题,新挑战
如果说在支付系统中使用设计模式,以及开发自定义协议的物联网这两类应用还不够酷的话,那么接下来,咱们就来学一点高逼格的技术吧。 在互联网已经日益普遍的时代,不管是开发2C应用还是2B应用,相信大部分的开发者都有过处理复杂业务逻辑的经历,比如电商、社交、电子政务、O…...
Oracle-00-卸载篇
这里给出企业级的Oracle 10g的卸教程,新安装的19c并没有正经去做卸载的操作,为了后面教程的进度,这里就先借用下10g,如果有需要会重新更新19c的卸载教程 windows服务中将Oracle所有服务全部停掉 选中Oracle - OraDb10g_home2->Oracle Installation Products->Univers…...
Java线程池使用与原理解析1(线程池优点、使用方法、参数含义及线程池运转机制)
为什么要使用线程池? JDK1.5后JUC包添加了线程池相关接口,在Java诞生之初并没有线程池这个概念。刚开始Java程序都是自行创建线程去处理任务。随着应用使用的线程越来越多,JDK开发者们发现有必要使用一个统一的类来管理这些线程,…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
