合并K个升序链表

题目

解法一

优先级队列

思想

将每个链表中的一个节点存放到优先级队列中,本题采用小根堆,将小根堆中的根节点取出,插入到最终的链表中,并且将该节点在原链表中的下一个节点插入小根堆中(需要向下调整),直到堆中没有节点为止(即所以链表都已经合并完)。

代码
class Solution {
public:struct Less{bool operator()(ListNode* l1,ListNode* l2){return l1->val > l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* node=new ListNode(0);ListNode* cur=node;priority_queue<ListNode*,vector<ListNode*>,Less> q;for(auto& it:lists){if(it) q.push(it);}while(!q.empty()){ListNode* tmp=q.top();q.pop();cur->next=tmp;if(tmp->next) q.push(tmp->next);cur=cur->next;}return node->next;}
};
解法二

归并/分治

思想

将链表两两进行合并,直到合并为一个链表为止。

代码
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return mergeL(lists,0,lists.size()-1);}ListNode* mergeL(vector<ListNode*>& lists,int l,int r){if(l>r) return nullptr;if(l==r) return lists[l];int mid=(l+r)>>1;ListNode* l1=mergeL(lists,l,mid);ListNode* l2=mergeL(lists,mid+1,r);return merge2L(l1,l2);}ListNode* merge2L(ListNode* l1,ListNode* l2){if(l1==nullptr) return l2;if(l2==nullptr) return l1;if(l1->val < l2->val){l1->next=merge2L(l1->next,l2);return l1;}else{l2->next=merge2L(l1,l2->next);return l2;}}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328256.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python查询和操作HTML文档库之pyquery使用详解

概要 在Web开发和数据抓取中,处理HTML文档是一项常见任务。Python的pyquery库提供了一个强大且灵活的方式来查询和操作HTML文档,类似于jQuery的语法。通过这篇文章,将深入了解pyquery的安装、特性、基本和高级功能,以及它在实际应用中的用例。 安装 安装pyquery相当简单,…

python:SunMoonTimeCalculator

# encoding: utf-8 # 版权所有 2024 ©涂聚文有限公司 # 许可信息查看&#xff1a; # 描述&#xff1a; https://github.com/Broham/suncalcPy # Author : geovindu,Geovin Du 涂聚文. # IDE : PyCharm 2023.1 python 3.11 # Datetime : 2024/5/14 21:59 # User …

MQTT_服务器的安装_1.3

此例子是以Windows系统安装开源版本的EMQX 下载 EMQX 下载并解压 解压如图 进入bin 文件夹在文件目录中输入cmd回车 启动服务器 然后在cmd中输入下面的代码&#xff08;会弹出一个访问网络的选项&#xff0c;确认可以访问网络&#xff09; emqx start 结果如图&#xff08;…

在Linux中安装Docker

如果之前安装过旧版本的 Docker&#xff0c;可以使用下面命令卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-selinux \docker-engine-selinux \docker-engine…

YOLO损失函数——SIoU和Focal Lossr损失函数解析

1. 概述 YOLO&#xff08;You Only Look Once&#xff09; 系列模型以其实时目标检测能力而闻名&#xff0c;其有效性在很大程度上归功于其专门设计的损失函数。在本文中&#xff0c;这里将深入探讨YOLO演进中不可或缺的各种YOLO损失函数&#xff0c;并重点介绍它们在PyTorch中…

免费泛域名证书申请

通配符证书是一种 SSL/TLS 证书&#xff0c;可用于保护多个域&#xff08;主机&#xff09;&#xff0c;由域名字段中的通配符 (*) 指示。 如果您有很多需要保护的域或子域&#xff0c;这会很有帮助&#xff0c;因为它可以节省您的时间和金钱。 本文将讨论通配符证书、它们的工…

代码复现|Demucs Music Source Separation

一、背景介绍 Demucs是一个开源的音源分离项目。 Demucs在算法层面前后经历了三次大版本的进化&#xff0c;最原始的V1版本是&#xff1a;编解码LSTM。具体算法原理图如下所示。该版本在时域进行音源分离。关于阅读笔记请点击这篇文章。 V1版本原理图 V2版本是同时使用时域和频…

车牌检测识别功能实现(pyqt)

在本专题前面相关博客中已经讲述了 pyqt + yolo + lprnet 实现的车牌检测识别功能。带qt界面的。 本博文将结合前面训练好的模型来实现车牌的检测与识别。并用pyqt实现界面。最终通过检测车牌检测识别功能。 1)、通过pyqt5设计界面 ui文件如下: <?xml version="1…

Star CCM+创建报告与监测

前言 结合前文介绍&#xff0c;创建衍生零部件的目的是为了监测创建的点或者面的数据变化。如Star CCM衍生零部件的创建介绍&#xff0c;创建完所需的点或者面后&#xff0c;下一步就是对创建的点、面进行监测。 一 报告类型介绍 在Star中&#xff0c;通过创建报告来对监测的…

基于单片机的空气质量检测系统设计(51+4G版)-设计说明书

设计摘要&#xff1a; 本设计是基于单片机的空气质量检测系统设计涉及以下主要功能&#xff0c;旨在监测甲烷和一氧化碳的浓度&#xff0c;并在浓度过高时采取相应措施&#xff0c;以确保室内空气质量的安全。该系统使用传感器对甲烷和一氧化碳的浓度进行检测。传感器将收集到…

【环境安装】nodejs 国内源下载与安装以及 npm 国内源配置

前言 Node.js 是一个基于 Chrome V8 引擎构建的 JavaScript 运行时环境&#xff0c;它能够使 JavaScript 在服务器端运行。它拥有强大的包管理器 npm&#xff0c;使开发者能够轻松管理和共享 JavaScript 代码包。 在中国&#xff0c;由于众所周知的原因&#xff0c;我们可能会…

vscode对一些软件的调试插件。

vscode对一些软件的调试插件。 1、ae &#xff0c;f1然后选择运行 after effect 脚本 2、maya,右键send code to maya 3、max&#xff0c;ctrle运行脚本到max 4、unity 从在Visual Studio代码使用.NET的核心&#xff1a; 1、安装.NET Core SDK&#xff0c;链接: https://dotn…

【UE5.1 角色练习】01-使用小白人蓝图控制商城角色移动

目录 效果 步骤 一、导入资源 二、控制角色移动 三、更换角色移动动作 效果 步骤 一、导入资源 新建一个工程&#xff0c;然后在虚幻商城中将角色动画的相关资源加入工程&#xff0c;这里使用的是“动画初学者内容包”和“MCO Mocap Basics” 将我们要控制的角色添加进…

SuperBox设计出图的效率提升!新增内门自动开孔和垫高支架图纸输出功能

越来越多的配电箱项目要求带内门&#xff0c;内门不仅可以有效减少外界灰尘、异物进入配电箱内部&#xff0c;保障配电箱正常运行&#xff0c;还能够隔离操作人员意外触摸导电部件&#xff0c;减少触电事故的发生。但是配电箱在配置内门后&#xff0c;会给设计带来更多的要求&a…

web入门练手案例(一)

下面是一些web入门案例和实现的代码&#xff0c;带有部分注释&#xff0c;倘若代码中有任何问题或疑问&#xff0c;欢迎留言交流~ 新闻页面 案例描述&#xff1a; 互联网的发展使信息的传递变得方便、快捷&#xff0c;浏览新闻称为用户获取信息的重要渠道。下面将实现一个简…

详细教程!VMware Workstation Pro16 安装 + 创建 win7 虚拟机!

嚯嚯嚯&#xff0c;很多宝子都想拥有自己不同的操作系统环境&#xff0c;用于学习或项目搭建。买服务器费钱&#xff0c;虚拟机则成为了一个很好的选择。本文详细介绍VMware Workstation Pro 16安装及win7虚拟机创建&#xff0c;保姆级教程奉上&#xff01; 一、准备工作 VMw…

掏心经验分享,软考中项0基础入门篇!

想备考下半年中项&#xff08;系统集成项目管理工程师&#xff09;的朋友&#xff0c;不知道如何了解软考中项&#xff0c;今天给大家整理一篇关于我自己在备考软考时的一些考量和踩过的一些坑。&#xff08;无广&#xff0c;放心看&#xff09; 很多小伙伴总是听大家说软考中…

Linux 服务器配置共享文件夹(NFS)

一、准备三台 linux 服务器 三台服务器: manger:172.16.11.178 ap1:172.16.11.179 ap2:172.16.11.180 /root/serverfiles/ 为共享目录 二、配置步骤 1、在服务端01的机器上安装nfs和rpcbind程序 yum -y install nfs* yum -y install rpcbind* 2、在安装完nfs以及rpcb…

Leecode热题100---11:盛最多水的容器

题目&#xff1a; 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;你不能倾…

使用单目相机前后帧特征点匹配进行3D深度估计的方法

在计算机视觉和机器人领域&#xff0c;三维空间感知是实现环境理解和交互的核心技术之一。特别是在资源受限的场合&#xff0c;使用针孔模型的单目相机进行深度估计成为了一种既经济又实用的解决方案。单目深度估计技术依赖于从连续视频帧中提取和匹配特征点&#xff0c;以估计…