LeetCode--23. 合并 K 个升序链表【堆和分治】
23. 合并 K 个升序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
正文
这道题有多种解决方案
堆
比较容易,又比较直观的就是堆排序,将每个节点加入最小根堆中,依次弹出加入最后的链表,就可得出答案,事实上,并不需要每次都将所有链表加入,只需要最开始将每个链表的头节点加入,然后在弹出链表时,直接将弹出的节点的下一个节点再加入堆即可,这样能够有效节省空间。
代码如下:
func mergeKLists(lists []*ListNode) *ListNode {lh := &ListHeap{}heap.Init(lh)for _, node := range lists {if node != nil {heap.Push(lh, node)}}dummy := &ListNode{}tmp := dummyfor lh.Len() > 0 {Node := heap.Pop(lh).(*ListNode)tmp.Next = Nodetmp = tmp.Nextif Node.Next != nil {heap.Push(lh, Node.Next)}}return dummy.Next
}type ListHeap []*ListNodefunc (l *ListHeap) Len() int {return len(*l)
}func (l *ListHeap) Less(i, j int) bool {return (*l)[i].Val < (*l)[j].Val
}func (l *ListHeap) Swap(i, j int) {(*l)[i], (*l)[j] = (*l)[j], (*l)[i]
}func (l *ListHeap) Push(x any) {*l = append(*l, x.(*ListNode))
}func (l *ListHeap) Pop() any {res := (*l)[len(*l)-1]*l = (*l)[:len(*l)-1]return res
}
堆排序不用ide也太难写了~
分治
跟归并排序的思路类似,将链表切片分成两部分,分别合并成一个链表,再将这两个链表进行合并。
可以理解为:
链表1 链表2 链表3 链表4| | | || | | || | | || | | |+————+————+ +————+————+| |链表 链表+————————+——————+||最终链表
代码如下:
func mergeKLists(lists []*ListNode) *ListNode {return Merge(lists, 0, len(lists) - 1)
}func Merge(lists []*ListNode, l int, r int) *ListNode {if l == r {return lists[l]} else if l > r {return nil}mid := (l + r) / 2return MergeTwoLists(Merge(lists, l, mid), Merge(lists, mid + 1, r))
}func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {dummy := &ListNode{}tmp := dummyfor list1 != nil && list2 != nil {if list1.Val > list2.Val {tmp.Next = list2tmp = tmp.Nextlist2 = list2.Next} else {tmp.Next = list1tmp = tmp.Nextlist1 = list1.Next}}if list1 != nil {tmp.Next = list1}if list2 != nil {tmp.Next = list2}return dummy.Next
}
相关文章:
LeetCode--23. 合并 K 个升序链表【堆和分治】
23. 合并 K 个升序链表 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 正文 这道题有多种解决方案 堆 比较容易,又比较直观的就是堆排序,将每个节点加入最小根堆中&…...
tp6上传文件大小超过了最大值+验证文件上传大小和格式函数
问题: 最近用tp6的文件上传方法上传文件时报文件过大错误。如下所示: $file $this->request->file(file);{"code": 1,"msg": "上传文件大小超过了最大值!","data": {"code": 1,&q…...
解决 Mac 只显示文件大小,不显示目录大小
前言 在使用 mac 的时候总是只显示文件的大小,不显示文件夹的大小,为了解决问题可以开启“计算文件夹”。 步骤 1.进入访达 2.工具栏点击“显示”选项,点击 “查看显示选项” 3.勾选 显示“资源库"文件夹 和 计算所有大小 或者点击…...
分布式大语言模型服务引擎vLLM论文解读
论文地址:Efficient Memory Management for Large Language Model Serving with PagedAttention 摘要 大语言模型(LLMs)的高吞吐量服务需要一次对足够多的请求进行批处理。然而,现有系统面临困境,因为每个请求的键值…...
快速入门——Vue框架快速上手
学习自哔哩哔哩上的“刘老师教编程”,具体学习的网站为:8.Vue框架快速上手_哔哩哔哩_bilibili,以下是看课后做的笔记,仅供参考。 第一节:前端环境准备 编码工具VSCode【www.code.visualstudio.com】/WebStorm也可&am…...
机器学习,我们主要学习什么?
机器学习的发展历程 机器学习的发展历程,大致分为以下几个阶段: 1. 起源与早期探索(20世纪40年代-60年代) 1949年:Hebb提出了基于神经心理学的学习机制,开启了机器学习的先河1950年代:机器学习的…...
安卓burp抓包,bypass ssl pinning
好久好久没有发东西了。主要是懒。。。 这几天在搞apk渗透,遇到了burp无法抓包问题,觉得可以写下来。 问题描述 1. 一台安卓手机,装了面具,可以拿到root 2. 电脑上有burp,设置代理 3.手机和电脑连同一个网段&…...
【如何基于Debian构建Kali Linux】
如何基于Debian构建Kali Linux 修改apt源获取Kali的apt密钥更新并安装Kali Linux软件包添加非root用户 在Linux系统的应用领域中,Kali Linux因其在渗透测试、安全审计等方面的出色表现而备受关注。Kali Linux是一个基于Debian的Linux发行版。接下来,将介…...
Hopper架构 GEMM教程
一 使用 1.1 makefile compile:nvcc -arch=sm_90a -lcuda -lcublas -std=c++17 matmul_h100_optimal.cu -o testrun:./test加入-lcublas,不然会有函数无法被识别 二 代码分析 2.1 kernel外参数分析 2.1.1 基本参数 constexpr int BM = 64*2;constexpr int BN = 256;cons…...
CV -- 基于GPU版CUDA环境+Pycharm YOLOv8 目标检测
目录 下载 CUDA 下载 cuDNN 下载 anaconda 安装 PyTorch pycharm 搭配 yolo 环境并运行 阅读本文须知,需要电脑中有 Nvidia 显卡 下载 CUDA 打开 cmd ,输入 nvidia-smi ,查看电脑支持 CUDA 版本: 我这里是12.0,进入…...
ELK8.17部署(Ubantu24x64)
检查java环境 ELK8.x不支持java8 若无环境可执行 sudo apt install openjdk-17-jre-headless 准备安装包 官网下载地址: ELK products 搜Elasticsearch、Kibana、Logstash、Filebeat versions需一致,这里使用8.17.0 Elasticsearch Kibana Logstash Filebeat e…...
Python glob模块使用示例代码
Python 的 glob 模块位于标准库中,专门用于在文件系统中进行 文件路径模式匹配(与 Shell 中的通配符匹配类似)。它可以根据 通配符(如 *、? 和 [])来查找符合条件的文件路径。 1. glob 模块的核心功能 路径模式匹配:根据指定的通配符模式,匹配对应的文件路径。递归搜索…...
npm、pnpm和yarn有什么区别
1. 性能和速度 npm:在较早的版本中,速度较慢,尤其是在安装大型依赖集时。自npm 5以后的版本引入了缓存机制,性能有所提升。yarn:由Facebook开发,主要目标是提高安装速度。使用了缓存和并行安装(…...
Java 基础面试
final、finalize 和 finally 的不同之处? Final:是一个修饰符,可以修饰变量、方法和类。如果 final 修饰变量,意味着该变量的值在初始化后不 能被改变。Finalize:方法是在对象被回收之前调用的方法, 给对象…...
ac的dhcp池里option43配错导致ap无法上线问题排查过程
dhcp池里ac地址配错,导致ap无法上线问题排查过程 问题:ap手动设置ac的ip正常注册在线,但dhcp获得ip和ac地址发现无法在ac上注册成功。 组网: ac旁路结构,路由器lan口地址172.16.1.1,开dhcp服务࿰…...
第1章:LangChain4j的聊天与语言模型
LangChain4J官方文档翻译与解析 目标文档路径: https://docs.langchain4j.dev/tutorials/chat-and-language-models/ 语言模型的两种API类型 LangChain4j支持两种语言模型(LLM)的API: LanguageModel:这种API非常简单,…...
Cython学习笔记1:利用Cython加速Python运行速度
Cython学习笔记1:利用Cython加速Python运行速度 CythonCython 的核心特点:利用Cython加速Python运行速度1. Cython加速Python运行速度原理2. 不使用Cython3. 使用Cython加速(1)使用pip安装 cython 和 setuptools 库(2&…...
【从0做项目】Java音缘心动(1)———项目介绍设计
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 零:项目结果展示 一:音乐播放器Web网页介绍 二:前期准备工作&…...
智慧农业新生态 | 农业数字化服务平台——让土地生金,让服务无忧
一部手机管农事,从播种到丰收,全链路数字化赋能! 面向农户、农机手、农服商、农资商打造的一站式农业产业互联网平台,打通农资交易、农机调度、农服管理、技术指导全场景闭环,助力乡村振兴提效增收。 三大核心场景&am…...
C++编程,#include <iostream>详解,以及using namespace std;作用
在C编程中,#include <iostream> 是用来包含输入/输出流头文件的预处理指令。它允许程序使用标准的输入/输出对象如 std::cout 和 std::cin,以便与标准输入和输出流进行交互。这一头文件是编写输入输出操作时必不可少的部分。 讲到这里,…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
游戏开发中常见的战斗数值英文缩写对照表
游戏开发中常见的战斗数值英文缩写对照表 基础属性(Basic Attributes) 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...
