【C++算法】54.链表_合并 K 个升序链表
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
题目链接:
23. 合并 K 个升序链表
题目描述:
解法
解法一:暴力解法
每个链表的平均长度为n,有k个链表,时间复杂度
O(nk^2)
合并两个有序链表
先把其中的两个链表有序合并,然后把合并后的链表和后面一个链表有序合并,每次合并两个直到结束。
解法二:利用优先级队列做优化
O(n*k*logk)
先给
n
个链表设置n
个指针,然后把每个链表的第一个指针放入小根堆里面,取走堆顶元素放入newhead
节点,哪一个链表的指针取走了就让那个链表指针的后一个位置放进小根堆,直到所有链表指针都指向NULL
。
解法三:归并排序,递归
O(n*k*logk)
C++ 算法代码:
解法二(利用堆)
/*** 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
{// 定义比较器结构体,用于小根堆的节点比较struct cmp{// 重载函数调用运算符,定义节点比较规则// 对于小根堆,我们需要大值返回true(表示优先级低)bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val; // 如果l1值大于l2,就向下调整,返回true,实现小根堆}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 创建一个小根堆,存储ListNode指针// 堆会根据节点的val值自动排序,最小的在堆顶// 第一个参数 ListNode*: 指定了队列中存储的元素类型,这里是链表节点的指针// 第二个参数 vector<ListNode*>: 指定了底层容器类型,这里使用vector存储ListNode指针// 第三个参数 cmp: 指定了元素比较的方式,是一个自定义的比较器结构体priority_queue<ListNode*, vector<ListNode*>, cmp> heap;// 将所有链表的头节点加入小根堆// 只有非空链表的头节点才会被加入// auto l 会依次获取数组中的每个元素,即每个链表的头指针for(auto l : lists)if(l) heap.push(l);// 创建虚拟头节点,简化链表构建过程ListNode* ret = new ListNode(0);ListNode* prev = ret; // 使用prev作为结果链表的尾指针// 不断从堆中取出最小节点,加入结果链表while(!heap.empty()){ListNode* t = heap.top(); // 取出堆顶元素(当前所有节点中值最小的)heap.pop(); // 移除堆顶元素prev->next = t; // 将最小节点添加到结果链表prev = t; // 更新尾指针// 如果当前取出的节点还有下一个节点,将其加入堆中if(t->next) heap.push(t->next);}// 获取结果链表的头节点(跳过虚拟头节点)prev = ret->next;delete ret; // 释放虚拟头节点return prev; // 返回合并后的链表头}
};
解法三(递归/分治)
/*** 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:ListNode* mergeKLists(vector<ListNode*>& lists) {// 主函数入口:调用递归函数处理整个链表数组return merge(lists, 0, lists.size() - 1);}// 分治递归函数:合并区间[left, right]内的链表ListNode* merge(vector<ListNode*>& lists, int left, int right){// 边界情况:如果left大于right,说明没有链表可合并if(left > right) return nullptr;// 边界情况:如果只有一个链表,直接返回if(left == right) return lists[left];// 1. 计算中间位置,将链表数组分为两部分int mid = left + right >> 1; // 等价于 (left + right) / 2// 2. 递归处理左右两个区间// 左区间: [left, mid]ListNode* l1 = merge(lists, left, mid);// 右区间: [mid + 1, right]ListNode* l2 = merge(lists, mid + 1, right);// 3. 合并两个区间返回的链表return mergeTowList(l1, l2);}// 合并两个有序链表ListNode* mergeTowList(ListNode* l1, ListNode* l2){// 处理边界情况if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;// 创建一个临时头节点,简化合并逻辑ListNode head;ListNode* cur1 = l1; // 指向第一个链表的当前节点ListNode* cur2 = l2; // 指向第二个链表的当前节点ListNode* prev = &head; // 指向合并结果的尾节点head.next = nullptr; // 初始化临时头节点// 合并两个链表,每次取值较小的节点while(cur1 && cur2){if(cur1->val <= cur2->val){// 第一个链表的当前节点值更小,加入结果prev = prev->next = cur1;cur1 = cur1->next;}else{// 第二个链表的当前节点值更小,加入结果prev = prev->next = cur2;cur2 = cur2->next;}}// 处理剩余节点(只需处理一个链表的剩余部分)if(cur1) prev->next = cur1;if(cur2) prev->next = cur2;// 返回合并后的链表头节点return head.next;}
};
相关文章:
【C++算法】54.链表_合并 K 个升序链表
文章目录 题目链接:题目描述:解法C 算法代码: 题目链接: 23. 合并 K 个升序链表 题目描述: 解法 解法一:暴力解法 每个链表的平均长度为n,有k个链表,时间复杂度O(nk^2) 合并两个有序…...
阿里云CDN应对DDoS攻击策略
阿里云CDN遭遇DDoS攻击时,可通过以下综合措施进行应对,保障服务的稳定性和可用性: 1. 启用阿里云DDoS防护服务 阿里云提供专业的DDoS防护服务,通过流量清洗中心过滤恶意流量,确保合法请求正常传输。该服务支持按需选…...
MySQL8的索引跳跃扫描原理
#MySQL 8 的索引跳跃扫描(Index Skip Scan)原理 1. 什么是索引跳跃扫描?索引跳跃扫描(Index Skip Scan)是 MySQL 8.0.13 引入的一种优化技术,允许在某些情况下跳过联合索引的最左前缀字段,仍然…...
centos 启动nginx 服务器
✅ 如果你是通过 yum 安装的 Nginx(推荐方式): 🔹 启动 Nginx: sudo systemctl start nginx 🔹 设置开机自启(建议开启): sudo systemctl enable nginx ὓ…...
格式化输出
% 符号相关 数据类型代码 %s:字符串 示例:print("名字是 %s" % "Tom") → 名字是 Tom%c:字符/ASCII码 示例:print("%c" % 65) → A%d/%i:有符号整数 示例:print("年龄…...
[leetcode]动态规划:斐波那契数列
一.线性dp 1.0什么是线性dp 线性DP就是指状态的转移具有线性递推关系,每个状态只依赖之前的状态,按照线性顺序一步步递推下去。 1.1斐波那契数列问题 #include <iostream> #include <vector> using namespace std; int main() { in…...
HackMyVM - todd记录
HackMyVM - toddhttps://mp.weixin.qq.com/s/E_-hepdfY-0veilL1fl2QA...
【spark认任务提交】配置优先级顺序
配置优先级顺序 Spark-submit 命令行参数 (最高优先级)代码中通过 SparkConf 设置的参数 (在应用程序中直接设置)spark-defaults.conf 文件中的配置 实际应用中的建议 固定配置:将集群级别的默认配置放在 spark-defaults.conf 中应用特定配置:将应用特…...
如何建立高效的会议机制
建立高效的会议机制需做到:明确会议目标、制定并提前分发议程、控制会议时长、确保有效沟通与反馈、及时跟进执行情况。其中,明确会议目标是核心关键,它直接决定了会议的方向与效率。只有明确目标,会议才不会偏离初衷,…...
spark Core-RDD转换算子
1. map算子:对RDD中的数据逐条进行映射转换,可实现类型或值的转换。函数签名为 def map[U: ClassTag](f: T > U): RDD[U] 。 2. mapPartitions算子:以分区为单位处理数据,可进行任意处理。与 map 相比, map 是分区内…...
【图像处理】C++实现通用Raw图转Unpack14的高效方法
一、需求背景 在图像处理领域,我们经常需要处理各种位深的原始数据(如Raw8、Unpack10等)。某些高端相机或传感器会输出14位精度的图像数据,但受传输限制,实际存储时可能采用低位深打包。本文将实现一个通用转换函数&a…...
Vue3的Composition API与React Hooks有什么异同?
Vue3的一个重大更新点就是支持Composition API,而且也被业界称为hooks,那么Vue3的“Hooks”与React的Hooks有这么区别呢? 一、核心相似点 1. 逻辑复用与代码组织 都解决了传统类组件或选项式 API 中逻辑分散的问题,允许将相关逻…...
Gerrit的安装与使用说明(Ubuntu)
#本页面按192.168.60.148服务器举例进行安装配置 1.权限配置 ## 使用root或者有sudo权限用户执行 # 创建gerrit用户 sudo useradd gerrit # 设置gerrit用户的密码 sudo passwd gerrit # 增加sudo权限 sudo visudo 在root ALL(ALL:ALL) ALL行下添加如下内容 gerrit ALL(ALL:…...
如何在Git历史中抹掉中文信息并翻译成英文
如何在Git历史中抹掉中文信息并翻译成英文 在软件开发和版本控制领域,维护一个清晰、一致的代码历史记录是至关重要的。然而,有时我们可能会遇到需要修改历史提交的情况,比如删除敏感信息或修正错误。本文将详细探讨如何在Git历史中抹掉中文…...
Ubuntu利用docker将ONNX模型转换为RK3588模型
1.安装docker 下载教程 1.拉取镜像 方法一:通过命令拉取 # 下载官方Docker镜像sudo docker pull registry.cn-hangzhou.aliyuncs.com/rockchip/rknn-toolkit2:v2.3.0 方法二:通过rknn-toolkit2自带的直接安装 2.开始工作 创建工作目录并复制ONNX模型…...
Go:入门
文章目录 Hello, World命令行参数找出重复行GIF动画获取一个URL并发获取多个URL一个 Web 服务器其他 Hello, World Hello world package main import "fmt" func main() {fmt.Println("Hello, 世界") }package main表明这是一个可独立执行的程序包&#…...
深入理解 ResponseBodyAdvice 及其应用
ResponseBodyAdvice 是 Spring MVC 提供的一个强大接口,允许你在响应体被写入 HTTP 响应之前对其进行全局处理。 下面我将全面介绍它的工作原理、使用场景和最佳实践。 基本概念 接口定义 public interface ResponseBodyAdvice<T> {boolean supports(Metho…...
SpringBoot对接火山引擎大模型api实现图片识别与分析
文章目录 一、前言二、创建应用三、后端1.SDK集成2.调用Rest API 四、前端 一、前言 Spring AI实战初体验——实现可切换模型AI聊天助手-CSDN博客 如上,在上一篇博客,我们已经实现了spring ai对接本地大模型实现了聊天机器人,但是目前有个新…...
Java ---成员,局部变量与就近原则
成员变量 声明在类内部,但在方法、构造器或代码块之外的变量。 属于类的实例(对象)或类本身(静态变量)。 实例变量(非静态成员变量): public class Person {private String name…...
基于libevent写一个服务器(附带源码)
使用libevent搭建服务器 服务器源码二级目录 使用开源框架,目的是减少程序员对一些精细的操作的误操作,也是为了让程序员能更好的对接业务而不是底层api的使用。 为何使用libevent,因为libevent开源已经有十几年了,能很好的承受数…...
2.2.3 Spark Standalone集群
搭建Spark Standalone集群需要完成多个步骤。首先,配置主机名、IP地址映射、关闭防火墙和SeLinux,并设置免密登录。接着,配置JDK和Hadoop环境,并在所有节点上分发配置。然后,下载并安装Spark,配置环境变量和…...
每天记录一道Java面试题---day38
说说类加载器双亲委派模型 回答重点 AppClassLoader的父加载器是ExtClassLoader,ExtClassLoader的父加载器是BootStrapClassLoader。JVM在加载一个类时,会调用AppClassLoader的laodClass方法来加载这个类,不过在这个方法中,会先…...
[ctfshow web入门] web33
信息收集 相较于上一题,这题多了双引号的过滤。我猜测这一题的主要目的可能是为了不让使用$_GET[a]之类的语句,但是$_GET[a]也是一样的 没有括号可以使用include,没有引号可以使用$_GET 可以参考[ctfshow web入门] web32,其中的所…...
【时时三省】(C语言基础)用switch语句实现多分支选择结构
山不在高,有仙则名。水不在深,有龙则灵。 ----CSDN 时时三省 if语句只有两个分支可供选择,而实际问题中常常需要用到多分支的选择。例如,学生成绩分类(85分以上为A等,70 ~ 84分为B等,60 ~ 69分为C等)&…...
为您的 Web 应用选择最佳文档阅读器
为显示选择合适的文档查看器是开发 Web 应用过程中至关重要的一步。文档查看器应能在提供功能性的同时,确保用户体验的流畅性。 开发人员必须评估多种因素,以确保效率、性能和兼容性。本文将帮助您了解影响用户文档浏览体验成功与否的关键指标。 渲染质…...
js逆向入门图灵爬虫练习平台第六题
地址:aHR0cHM6Ly9zdHUudHVsaW5ncHl0b24uY24vcHJvYmxlbS1kZXRhaWwvNi8 观察可以发现请求头有有字段加密和响应结果加密 查看启动器 开始断点调试 直接复制里面的js内容,测试函数...
招商蛇口 | 回归生活本身,革新CID的143㎡改善标准
时光流转,城市向前。在西安这片千年文脉的沃土之上,招商蛇口已深耕11载,用21座标杆作品,为17000余户家庭筑就理想栖居。从曲江到高新,从城市更新到人居焕新,每一座作品都是对“美好生活承载者”使命的践行。…...
第6课:分布式多智能体系统架构
分布式多智能体系统架构:从算力协同到微服务部署的工程化实践 一、引言:当智能体规模突破百级:分布式架构为何成为必选项? 在多智能体系统(MAS)从“实验室Demo”走向“工业级应用”的过程中,传…...
Vue3 Teleport 深度解析与面试技巧
Vue3 Teleport 深度解析与面试技巧 一、Teleport 核心价值解析 1.1 诞生背景与设计哲学 DOM层级困境:传统组件树与视觉层级的矛盾样式污染问题:z-index层级管理的世纪难题逻辑解耦需求:业务逻辑与DOM结构的正交性要求 1.2 核心能力矩阵 能…...
断言与反射——以golang为例
断言 x.(T) 检查x的动态类型是否是T,其中x必须是接口值。 简单使用 func main() {var x interface{}x 100value1, ok : x.(int)if ok {fmt.Println(value1)}value2, ok : x.(string)if ok {//未打印fmt.Println(value2)} }需要注意如果不接受第二个参数就是OK,这…...
react函数组件中,className字符串、style对象如何在父子组件之间传递
一、需要传递的样式在父组件的scss文件中提前写好 子组件的dom解析后: 二、向子组件直接传递style对象...
WHAT - React Portal 机制:将子组件渲染到 DOM 的指定节点
文章目录 适合场景基本语法示例:Modal 弹窗1. 创建一个简单的 Modal.tsx2. 在 App 中使用 为什么要用 Portal?TypeScript 中 Portal 类型定义? 适合场景 React Portal 是 React 提供的一种机制,让你可以将子组件渲染到 DOM 的指定…...
企业绿电消纳比例不达标?安科瑞微电网智慧能源平台助力企业低碳转型
方案配置支持请联系安科瑞电气周女士 企业绿电消纳政策是国家推动能源转型和实现“双碳”目标的重要抓手,近年来政策体系逐步完善。企业通过建设“源网荷储”一体化项目、虚拟电厂等技术,提升绿电消纳能力。 一、安科瑞提供解决方案 深耕用电业务&…...
uni-app初学
文章目录 1. pages.json 页面路由2. 图标3. 全局 CSS4. 首页4.1 整体框架4.2 完整代码4.3 轮播图 swiper4.3.1 image 4.4 公告4.4.1 uni-icons 4.5 分类 uni-row、uni-col4.6 商品列表 小程序开发网址: 注册小程序账号 微信开发者工具下载 uniapp 官网 HbuilderX 下…...
网络划分vlan隔离
隔离划分 比如我们想要将pc1和pc2隔离,我们只需在lsw1交换机中,如下配置: sys 先进入系统视图 先后输入 代表创建2个隔离区 vlan 10 vlan 20 然后进入0/0/1、0/0/2设置隔离类型,并划分隔离区域 int gi0/0/01 port l…...
HDCP(四)
HDCP驱动开发实战深度解析 以下从协议栈架构、核心模块实现、安全设计到硬件集成,结合HDCP 2.x规范与主流硬件平台(如ARM、FPGA)特性,系统拆解驱动开发关键环节: 1. 协议栈架构与模块划分 驱动分层设计 硬件抽象层&…...
大数据(7.4)Kafka存算分离架构深度实践:解锁对象存储的无限潜能
目录 一、传统架构的存储困境与破局1.1 数据爆炸时代的存储挑战1.2 存算分离的核心价值矩阵 二、对象存储集成架构设计2.1 分层存储核心组件2.2 关键配置参数优化 三、深度集成实践方案3.1 冷热数据分层策略3.1.1 存储策略性能对比 3.2 跨云数据湖方案 四、企业级应用案例4.1 金…...
SLAM文献之SuMa++: Efficient LiDAR-based Semantic SLAM
SuMa是基于Surfel的SLAM算法SuMa的改进版本,通过引入语义分割信息提升动态环境下的鲁棒性和回环检测性能。以下从算法原理和公式推导两方面详细阐述: 一、SuMa算法原理 1. 基础:SuMa算法 SuMa使用Surfel(表面元素)构…...
react中通过 EventEmitter 在组件间传递状态
要在 Reply 组件中通过 statusChangeEvent 发送状态值,并在 Select 组件中接收这个状态值 status,你可以按照以下步骤实现: //Event.jsimport EventEmitter from events;export const statusChangeEvent new EventEmitter();// 工单状态切换…...
机器学习 从入门到精通 day_03
1. KNN算法-分类 1.1 样本距离判断 明可夫斯基距离:欧式距离,明可夫斯基距离的特殊情况;曼哈顿距离,明可夫斯基距离的特殊情况。 两个样本的距离公式可以通过如下公式进行计算,又称为欧式距离。 (…...
WHAT - React 两个重要的 Typescript 类型:ReactNode vs JSX.Element
文章目录 ReactNode 是什么?示例用途 JSX.Element 是什么?示例用途 ReactNode vs JSX.Element 对比使用建议其他相关类型例子总结 这两个类型 ReactNode 和 JSX.Element 在 React TypeScript 中经常出现,但它们含义不同,适用场景…...
了解 DeFi:去中心化金融的入门指南与未来展望
去中心化金融,或 DeFi,代表着全球金融体系运作方式的革命性转变。它是一个总称,指的是一个不断增长的去中心化应用程序(dapp)、协议和平台生态系统,这些生态系统构建在公共区块链网络上,无需传统…...
四旋翼无人机手动模式
无人机的手动模式(Manual Mode)是指飞手完全通过遥控器手动控制无人机的飞行姿态、高度、方向和速度,无需依赖自动稳定系统或辅助功能(如GPS定位、气压计定高、视觉避障等)。这种模式赋予操作者最大的操控自由度&a…...
航电系统之驱动系统篇
航电系统的驱动系统是航空电子系统中负责为各类电子设备、传感器、执行机构及控制模块提供稳定、可靠电能的关键部分。其核心功能在于将飞机电源系统的电能转换为适合航电设备使用的形式,确保航电系统在各种飞行条件下正常运行。以下从组成结构、工作原理、技术特点…...
《嵌入式开发实战:基于Linux串口的LED屏显系统设计与实现》
一、项目概述 本文介绍如何通过Linux系统的串口通信,驱动工业级LED显示屏实现动态数据展示。项目采用C语言开发,包含气象数据显示和实时时钟两大核心功能,涉及以下关键技术点: 串口通信协议配置 自定义数据帧封装 CRC16校验算法…...
记录一下移动端uView动态表单校验
uni-app开发uView必不可少,uView是uni-app生态专用的UI框架。 像element-ui一样uView也有自己的表单组件u-form。 对于下图这种列表数据该如何做表单校验,官方文档好像没有具体的案例,记录一下。 问题: 主要实现步骤:…...
Django项目入门二
Django项目入门二 目录 1.修改部门数据 2.新增员工数据 3.修改员工数据 4.删除员工数据 一、修改部门数据 上一篇文章, 我们只剩下修改功能没有做了, 那在这篇文章, 我们给它补上。 在做之前, 我们需要对views.py文件进行调整, 由于我们考虑到有部门信息和员工信息, 如…...
Java创建Android自用证书
在 Android 开发中,如果需要创建一个自用的证书,可以使用 Java 开发工具包(JDK)自带的 keytool 工具。 KeystoreGenerator.java import java.io.BufferedReader; import java.io.File; import java.io.IOException; import java.…...
Redis——实现消息队列
目录 前言 基于List结构模拟消息队列 基于List实现消息队列优缺点 基于PubSub(订阅者)实现消息队列 示例 基于PubSub的消息队列的优缺点 基于Stream的消息队列 STREAM类型消息队列的XREAD命令特点: 基于Stream的消息队列-消费者组 基于…...
学习51单片机Day01---做实验前置一些内容
目录 一、前面要看的: 1.下载软件 2.如何开始做? 3.基本框架: 4.如何编译运行: 5.可以运行的样子: 6.怎么生成hex: 7.滴滴放到单片机上: 二、过程中可能出现的问题(一直会更…...