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

23. 合并 K 个升序链表

题目描述

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

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

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4

解答

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// 分治合并的方法// 若有k个链表,第一轮两两合并,得到 k/2 个链表 // 第二轮再两两合并,得 k / 4个链表,依此类推,剩余一个链表然后再自底向上合并ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* mergeKLists1(vector<ListNode*>& lists) {// 顺序合并ListNode *ans = nullptr; // 初始和一个空链表合并,便于操作for(size_t i = 0; i < lists.size(); ++i){ans = mergeTwoLists(ans, lists[i]);}return ans;}private:// 将 lists中下标从[l, r]的链表进行合并ListNode *merge(vector<ListNode*>& lists, int l, int r){if(l == r) return lists[l];if(l > r) return nullptr;int mid = (l + r) >> 1; // 拆分成两部分进行合并return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));}// 两个链表进行归并排序ListNode* mergeTwoLists(ListNode *a, ListNode *b){if((!a) || (!b)) return a ? a : b;ListNode head, *tail = &head, *aptr = a, *bptr = b;// 归并,尾插入列表while(aptr && bptr){if(aptr->val < bptr->val){tail->next = aptr;aptr = aptr->next;}else {tail->next = bptr;bptr = bptr->next;}tail = tail->next;}// 处理还有节点的链表,添加到结尾tail->next = aptr ? aptr : bptr;return head.next;}};

相关文章:

23. 合并 K 个升序链表

题目描述 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff1a;链表数组…...

Nexus3部署、配置+SpringBoot项目Demo

Docker部署Nexus 搜索Nexus3镜像&#xff1a;[rootlocalhost ~]# docker search nexus 拉取Nexus3镜像&#xff1a;[rootlocalhost ~]# docker pull sonatype/nexus3 启动Nexus3前查看虚拟机端口是否被占用&#xff1a;[rootlocalhost ~]# netstat -nultp 通过Docker Hub查看安…...

linux下用docker安装mysql

1.mysql Docker镜像 docker pull mysql:[版本号 或 latest]例&#xff1a;docker pull mysql:5.7 2.查看拉取的docker镜像 docker images3.设置 Docker 卷 docker volume create mysql-data列出 Docker 已知的所有卷 docker volume ls4.运行一个 MySQL Docker 容器 docke…...

Vue - 可视化用户角色、菜单权限、按钮权限配置(动态获取菜单路由)

GitHub Demo 地址 在线预览 前言 关于动态获取路由已在这里给出方案 Vue - vue-admin-template模板项目改造&#xff1a;动态获取菜单路由 这里是在此基础上添加了系统管理模块&#xff0c;包含用户管理&#xff0c;角色管理&#xff0c;菜单管理&#xff0c;字典管理&#xf…...

hive库操作示例

hive库操作示例 1、常规表 创建数据库 CREATE DATABASE mydatabase;使用数据库 USE mydatabase;创建表 CREATE TABLE mytable (id INT,name STRING,age INT ) ROW FORMAT DELIMITED FIELDS TERMINATED BY , STORED AS TEXTFILE;插入数据 INSERT INTO TABLE mytable VALUE…...

LeetCode第 N 个泰波那契数 (认识动态规划)

认识动态规划 编写代码代码空间优化 链接: 第 N 个泰波那契数 编写代码 class Solution { public:int tribonacci(int n) {if(n 0){return 0;}else{if(n 1 || n 2)return 1;}vector<int> dp(n 1);dp[0] 0;dp[1] 1;dp[2] 1;for(int i 3;i < n;i){dp[i] dp[i-3]…...

线程安全问题(内存可见性)

导致的原因 内存可见性问题的出现主要是因为编译器优化多线程导致的 示例代码 package 线程安全问题;import java.util.Scanner;/*** Created with IntelliJ IDEA.* Description:* User: wuyulin* Date: 2023-07-26* Time: 13:49*/ public class Demo2 {private volatile sta…...

STM32MX配置EEPROM(AT24C02)------保姆级教程

———————————————————————————————————— ⏩ 大家好哇&#xff01;我是小光&#xff0c;嵌入式爱好者&#xff0c;一个想要成为系统架构师的大三学生。 ⏩最近在开发一个STM32H723ZGT6的板子&#xff0c;使用STM32CUBEMX做了很多驱动&#x…...

微信小程序 样式和全局配置

WXSS wxss 把屏幕分为750个物理像素&#xff0c;大屏大&#xff0c;小屏小&#xff0c;随着设备不一致自动适配 推荐使用iPhone6作为标准&#xff0c;1个rpx 0.5个px&#xff0c;把px乘以2就是rpx的参数 import 导入外部样式表 import /common/common.wxss 样式 权重一…...

一.初识C语言

一.初识C语言 C语言标准规定&#xff1a; sizeof(long)>sizeof(int)就可以了变量要定义在当前代码块的最前面 #defin _CRT_SECURE_NO_WARNINGS 1#include <stdio.h> //包含一个stdio.h的文件 std-标准standard input outputint main() //主函数-程序的入口-main函数…...

filebeat到kafka示例

docker run -d \ --namefilebeat_7.14_0 \ #filebeat名称 --userroot \ --volume"/data/filebeat/filebeat.yml:/usr/share/filebeat/filebeat.yml" \ #映射filebeat.yml配置 --volume"/data/filebeat/log:/usr/share/filebeat/log" \…...

AlmaLinux系统下的Zabbix汉化

我安装的是zabbix下的虚拟机&#xff0c;安装完成后&#xff0c;直接可以打开网站了&#xff0c;但是界面是英文&#xff0c;看了设置&#xff0c;没有中文选项&#xff0c;就需要在系统中安装中文字符集了。 # locale -a #查看里面没有zh_CN之类的项 # dnf install -…...

【网络编程】(TCP流套接字编程 ServerSocket API Socket API 手写TCP版本的回显服务器 TCP中的长短连接)

文章目录 网络编程TCP流套接字编程ServerSocket APISocket APITCP中的长短连接手写TCP版本的回显服务器 网络编程 TCP流套接字编程 TCP提供的API主要是两个类:ServerSocket 和 Socket . TCP不需要一个类来表示"TCP数据报"因为TCP不是以数据报为单位进行传输的.是以…...

企业级PaaS低代码快开平台源码,基于 Salesforce Platform 的开源替代方案

PaaS低代码快开平台是一种快速开发应用系统的工具&#xff0c;用户通过少量代码甚至不写代码就可以快速构建出各种应用系统。 随着信息化技术的发展&#xff0c;企业对信息化开发的需求正在逐渐改变&#xff0c;传统的定制开发已经无法满足企业需求。低代码开发平台&#xff0…...

【LeetCode】72.编辑距离

题目 给你两个单词 word1 和 word2&#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作&#xff1a; 插入一个字符删除一个字符替换一个字符 示例 1&#xff1a; 输入&#xff1a;word1 "horse", word2 "…...

大模型,开源干不掉闭源

开源大模型对闭源大模型的冲击&#xff0c;变得非常猛烈。 今年3月&#xff0c;Meta发布了Llama&#xff08;羊驼&#xff09;&#xff0c;很快成为AI社区内最强大的开源大模型&#xff0c;也是许多模型的基座模型。有人戏称&#xff0c;当前的大模型集群&#xff0c;就是一堆各…...

Redis 九种数据类型的基本操作

一、redis9种数据类型的基本操作 ①key操作 #查找所有的key 127.0.0.1:6379> keys * 1) "pop" 2) "mylist" 3) "lpl" 4) "myset" #设置key的过期时间 返回1表示执行成功&#xff0c;0表示失败&#xff0c;出现问题 127.0.0.1:6379…...

爬取微博热搜榜并进行数据分析

设计方案 爬虫爬取的内容 &#xff1a;爬取微博热搜榜数据。 网络爬虫设计方案概述 用requests库访问页面用get方法获取页面资源&#xff0c;登录页面对页面HTML进行分析&#xff0c;用beautifulsoup库获取并提取自己所需要的信息。再讲数据保存到CSV文件中&#xff0c;进行…...

基于深度神经网络的肺炎检测系统实现

一、说在前面 使用AI进行新冠肺炎图像诊断可以加快病例的诊断速度&#xff0c;提高诊断的准确性&#xff0c;并在大规模筛查中发挥重要作用&#xff0c;从而更好地控制和管理这一流行病。然而&#xff0c;需要强调的是&#xff0c;AI技术仅作为辅助手段&#xff0c;最终的诊断决…...

C# LINQ和Lambda表达式对照

C# LINQ和Lambda表达式对照 1. 基本查询语句 Linq语法&#xff1a; var datafrom a in db.Areas select a ; Lamda语法&#xff1a; var datadb.Areas; sql语法&#xff1a; SELECT * FROM Areas2. 简单的WHERE语句 Linq语法&#xff1a; var datafrom a in db.orderI…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...