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

算法与数据结构(合并K个升序链表)

思路

有了合并两个链表的基础后,这个的一种方法就是可以进行顺序合并,我们可以先写一个函数用来合并两个链表,再在合并K个链表的的函数中循环调用它。

解题过程

解析这个函数

首先,可以先判断,如果a为空,则返回b。如果b为空,则返回a。

在合并链表时,我们需要一个head保存合并之后链表的头,我们可以把head设为一个虚拟的头(不保存val)。

其次,我们还需要一个指针(cur)记录下一个插入位置的前一个位置。

我们还需要设置pa,pb指针来对a,b链表进行遍历

当pa和pb都非空时:

若pa->val < pb->val,则将pa插入到cur的后面,pa向后移动一个。

若pa->val >= pb->val,则将pb插入到cur的后面,pb向后移动一个。

两个插入完之后,cur都需要向后移动一个,方便下次插入。

循环结束之后,运用三元运算符,若pa不为空,则cur直接接上pa剩下的。反之,接上pb。合并完链表后,返回head.next

遍历lists:

将空链表不断与list中的数据进行合并

最后返回ans。

代码

//顺序合并
class Solution {
public:ListNode* mergeTwoLists(ListNode* a, ListNode* b){if(!a)return b;if(!b)return a;ListNode head, *cur = &head, *pa = a, *pb = b;while(pa && pb){if(pa->val < pb->val){cur->next = pa;pa = pa->next;}else{cur->next = pb;pb = pb->next;}cur = cur->next;}cur->next = (pa ? pa : pb);return head.next;}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* ans = nullptr;for(int i = 0; i < lists.size();i++){ans = mergeTwoLists(ans, lists[i]);}return ans;}
};

相关文章:

算法与数据结构(合并K个升序链表)

思路 有了合并两个链表的基础后&#xff0c;这个的一种方法就是可以进行顺序合并&#xff0c;我们可以先写一个函数用来合并两个链表&#xff0c;再在合并K个链表的的函数中循环调用它。 解题过程 解析这个函数 首先&#xff0c;可以先判断&#xff0c;如果a为空&#xff0c…...

洛谷 P4552 [Poetize6] IncDec Sequence C语言

P4552 [Poetize6] IncDec Sequence - 洛谷 | 计算机科学教育新生态 题目描述 给定一个长度为 n 的数列 a1​,a2​,…,an​&#xff0c;每次可以选择一个区间 [l,r]&#xff0c;使这个区间内的数都加 1 或者都减 1。 请问至少需要多少次操作才能使数列中的所有数都一样&#…...

保姆级教程Docker部署Zookeeper官方镜像

目录 1、安装Docker及可视化工具 2、创建挂载目录 3、运行Zookeeper容器 4、Compose运行Zookeeper容器 5、查看Zookeeper运行状态 6、验证Zookeeper是否正常运行 1、安装Docker及可视化工具 Docker及可视化工具的安装可参考&#xff1a;Ubuntu上安装 Docker及可视化管理…...

javaEE-6.网络原理-http

目录 什么是http? http的工作原理&#xff1a; 抓包工具 fiddler的使用 HTTP请求数据: 1.首行:​编辑 2.请求头(header) 3.空行&#xff1a; 4.正文&#xff08;body&#xff09; HTTP响应数据 1.首行&#xff1a;​编辑 2.响应头 3.空行&#xff1a; 4.响应正文…...

【戒抖音系列】短视频戒除-1-对推荐算法进行干扰

如今推荐算法已经渗透到人们生活的方方面面&#xff0c;尤其是抖音等短视频核心就是推荐算法。 【短视频的危害】 1> 会让人变笨&#xff0c;慢慢让人丧失注意力与专注力 2> 让人丧失阅读长文的能力 3> 让人沉浸在一个又一个快感与嗨点当中。当我们刷短视频时&#x…...

9.建造者模式 (Builder Pattern)

定义 建造者模式&#xff08;Builder Pattern&#xff09;是一种创建型设计模式&#xff0c;旨在将复杂对象的构建过程与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。该模式的核心思想是通过一步步地构建一个复杂的对象&#xff0c;每个步骤独立且可扩展&…...

OpenCV:特征检测总结

目录 一、什么是特征检测&#xff1f; 二、OpenCV 中的常见特征检测方法 1. Harris 角点检测 2. Shi-Tomasi 角点检测 3. Canny 边缘检测 4. SIFT&#xff08;尺度不变特征变换&#xff09; 5. ORB 三、特征检测的应用场景 1. 图像匹配 2. 运动检测 3. 自动驾驶 4.…...

Clion开发STM32时使用stlink下载程序与Debug调试

一、下载程序 先创建一个文件夹&#xff1a; 命名&#xff1a;stlink.cfg 写入以下代码: # choose st-link/j-link/dap-link etc. #adapter driver cmsis-dap #transport select swdsource [find interface/stlink.cfg]transport select hla_swdsource [find target/stm32f4x.…...

电脑开机键一闪一闪打不开

家人们谁懂啊&#xff01;本来打算愉快地开启游戏时光&#xff0c;或者高效处理工作任务&#xff0c;结果按下电脑开机键后&#xff0c;它就只是一闪一闪的&#xff0c;怎么都打不开。相信不少朋友都遭遇过这种令人崩溃的场景&#xff0c;满心的期待瞬间化为焦急与无奈。电脑在…...

深度学习 Pytorch 基础网络手动搭建与快速实现

为了方便后续练习的展开&#xff0c;我们尝试自己创建一个数据生成器&#xff0c;用于自主生成一些符合某些条件、具备某些特性的数据集。 导入相关的包 # 随机模块 import random# 绘图模块 import matplotlib as mpl import matplotlib.pyplot as plt# 导入numpy import nu…...

Sqli-labs靶场实录(一):Basic Challenges

sqli-labs靶场实录:Basic Challenges sql手注基本流程Less-11.1探测注入点1.2判断字段数1.3判断回显位1.4提取数据库基本信息1.5拖取敏感数据 Less-2Less-3Less-4Less5爆表爆列名 Less6爆库爆表爆列名 Less7猜解数据库长度逐字符爆破数据库名 Less8爆库 Less9爆库 Less10Less11…...

2024最新版Node.js详细安装教程(含npm配置淘宝最新镜像地址)

一&#xff1a;Node.js安装 浏览器中搜索Nodejs&#xff0c;或直接用网址:Node.js — 在任何地方运行 JavaScript 建议此处下载长期支持版本&#xff08;红框内&#xff09;: 开始下载&#xff0c;完成后打开文件: 进入安装界面&#xff0c;在此处勾选&#xff0c;再点击n…...

RK3568使用QT搭建TCP服务器和客户端

文章目录 一、让RK3568开发板先连接上wifi二、客户端代码1. `widget.h` 文件2. `widget.cpp` 文件**详细讲解**1. **`Widget` 类构造函数 (`Widget::Widget`)**2. **UI 布局 (`setupUI`)**3. **连接按钮的槽函数 (`onConnectClicked`)**4. **发送消息按钮的槽函数 (`onSendMess…...

Android学习20 -- 手搓App2(Gradle)

1 前言 昨天写了一个完全手搓的&#xff1a;Android学习19 -- 手搓App-CSDN博客 后面谷歌说不要用aapt&#xff0c;d8这些来搞。其实不想弄Gradle的&#xff0c;不过想着既然开始了&#xff0c;就多看一些。之前写过一篇Gradle&#xff0c;不过是最简单的编译&#xff0c;不涉…...

LeetCode - Google 大模型10题 第2天 Position Embedding(位置编码) 3题

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/145454489 在 Transformer 架构中&#xff0c;位置编码(Position Embedding) 是辅助模型理解序列中元素顺序的关键机制。绝对位置编码(Absolute P…...

PostgreSQL 数据库备份与还原

为了安全与数据共享等&#xff0c;创建好的数据库有时候需要备份操作和还原操作。数据库的备份与还原主要是三个命令&#xff1a;pg_dump、pg_dumpall 和 pg_restore 。 其中pg_dump用于备份单个数据库&#xff0c;它支持多种备份格式&#xff08;SQL、自定义等&#xff09;&a…...

proxmox通过更多的方式创建虚拟机

概述 作为一名资深运维工程师&#xff0c;我们经常需要在 Proxmox 虚拟化平台上创建和管理虚拟机。本文将介绍三种不同的方式在 Proxmox 上创建 Ubuntu 虚拟机&#xff1a; 通过 Proxmox 命令创建虚拟机通过 Shell 脚本自动化创建虚拟机使用 Proxmox API 创建虚拟机 每种方式…...

WordPress使用(2)

上一篇文章讲述了WordPress的基本安装&#xff0c;主要是docker方式的处理。本文章主要介绍WordPress安装后的其他设置。 1. 安装后设置 安装后碰到的第一个需求就是安装一个合适的主题&#xff0c;但WordPress默认的上传文件大小是2M&#xff0c;远远无法满足要求&#xff0…...

git中文件的状态状态切换

文件的状态分类 Git 中文件的状态主要分为以下几种&#xff1a; Untracked&#xff08;未跟踪&#xff09; 定义&#xff1a;这些文件从未被 Git 跟踪过&#xff0c;通常是因为它们是新创建的文件&#xff0c;或者被 .gitignore 排除在外。 示例&#xff1a;新创建的文件 new…...

解决php8.3无法加载curl扩展

把它的值更改为扩展存在的目录的绝对路径(扩展存在的目录为有php_xxx.dll存在的目录) extension_dir "e:\serv\php83\ext" 然后从php根目录复制 libssh2.dll 和 libcrypto-*.dll 和 libssl-*.dll 到Apache根目录下的bin目录 重启apache服务即可...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...