【Python】 小顶堆:困难 Leetcode 23. 合并 K 个升序链表 -- Python中heapq对于自定义数据类型的比较

描述

给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]

代码

代码1

由于可能存在相同值的结点,当用元组或数组作为堆中元素时,会出现无法比较结点的情况。在这里解决的方法是每个元组中再添加进一个独一无二的id

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        node_heap = []
        dummy_node = ListNode(-float('inf'))
        dnode = dummy_node
        # 为了避免相同值的结点无法比较,每个结点配有独一的id
        id = 0
        for head in lists:
            if(not head): continue
            heappush(node_heap,(head.val,id,head))
            id += 1
        while(node_heap):
            node = heappop(node_heap)[2]
            if(node.next):
                heappush(node_heap,(node.next.val,id,node.next))
                id += 1
            dnode.next = node
            dnode = dnode.next
        return dummy_node.next

在这里插入图片描述

代码2

来自GPT:
在Python中,__lt__代表“less than”(小于)的缩写。这个特殊方法用于定义对象的“小于”比较运算符(<)的行为。Python中还有其他一些类似的特殊方法,如__gt__(greater than,大于)、__le__(less than or equal to,小于等于)、__ge__(greater than or equal to,大于等于)和__eq__(equal to,等于),它们分别用于定义不同的比较运算符的行为。
通过使用__lt__等方法,Python允许你自定义对象之间的比较行为,这样你就可以使用<、>、<=、>=和==等运算符来比较你的自定义对象。

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        ListNode.__lt__ = lambda self, other: self.val < other.val
        node_heap = []
        dummy_node = ListNode(114514)
        dnode = dummy_node

        for head in lists:
            if(head): heappush(node_heap,head)
        while(node_heap):
            node = heappop(node_heap)
            if(node.next): heappush(node_heap,node.next)
            dnode.next = node
            dnode = dnode.next
        return dummy_node.next

在这里插入图片描述不过这种性能似乎没之前那个好

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

构造函数和析构函数

目录 一&#xff1a;类的六个默认函数 二&#xff1a;构造函数 2.1概念 2.2特性 三&#xff1a;析构函数 3.1概念&#xff1a; 3.2特性 一&#xff1a;类的六个默认函数 如果一个类中什都没有&#xff0c;称为空类 空类中真的什么都没有吗?并不是&#xff0c;任何类在…

MySQL客户端安装并配置免密登录

最近在写脚本时需要向MySQL数据库中存储数据&#xff0c;且脚本运行的服务器与MySQL服务器不是同一台服务器&#xff0c;而且需要保证MySQL密码的安全性&#xff0c;不能在脚本中暴露&#xff0c;所以就需要在服务器上安装MySQL客户端&#xff0c;并配置免密登录。 一、虚拟机…

C++ List 到 Python List 的转换

当我们编写 C 库的封装器通常涉及使用一种跨语言的接口技术&#xff0c;比如使用C接口或者使用特定的跨语言库&#xff0c;比如SWIG&#xff08;Simplified Wrapper and Interface Generator&#xff09;或者Pybind11。这里我将简要介绍如何使用Pybind11来封装一个C库&#xff…

jenkins+docker实现可持续自动化部署springboot项目

目录 一、前言 二、微服务带来的挑战 2.1 微服务有哪些问题 2.2 微服务给运维带来的挑战 三、可持续集成与交付概述 3.1 可持续集成与交付概念 3.1.1 持续集成 3.1.2 持续交付 3.1.3 可持续集成与交付核心理念 3.2 可持续集成优点 3.3 微服务为什么需要可持续集成 四…

金三银四面试题(十五):Java基础问题(6)

这部分面试题多用于面试的热身运动&#xff0c;对很多找实习和准备毕业找工作的小伙伴至关重要。 HashMap与ConcurrentHashMap 都是key-value 形式的存储数据&#xff1b; HashMap 是线程不安全的&#xff0c;ConcurrentHashMap 是JUC 下的线程安全的&#xff1b; HashMap 底层…

降低笔记本电脑噪音的七种方法,看下有没有适合你的

序言 无论是玩游戏、浏览网络还是做严肃的工作,差不多都有这么一台笔记本电脑,它有足够的处理能力来处理几乎任何事情。不幸的是,它可能会变得非常大声,但有办法来遏制这种噪音。 清洁通风口和风扇,并使用硬表面 如果你的笔记本电脑现在比过去运行同样的软件时声音更大…

docker笔记(二):镜像、容器数据卷

四、 docker镜像 4.1 镜像 镜像是一种轻量级、可执行的独立软件包&#xff0c;用来打包软件运行环境和基于运行环境开发的软件&#xff0c;它包含运行某个软件所需的所有内容&#xff0c;包括代码、库、环境变量和配置文件 所有的应用&#xff0c;直接打包docker镜像就可以直…

深度学习500问——Chapter05: 卷积神经网络(CNN)(4)

文章目录 5.18 卷积神经网络凸显共性的方法 5.18.1 局部连接 5.18.2 权值共享 5.18.3 池化操作 5.19 全连接、局部连接、全卷积与局部卷积 5.20 局部卷积的应用 5.21 NetVLAD池化 参考文献 5.18 卷积神经网络凸显共性的方法 5.18.1 局部连接 我们首先了解一个概念&#xff0c…

Office办公软件之Excel的使用(一)

1、“开始”菜单中的部分属性 2、制作斜线表头 ctrl1,弹出设置单元格格式&#xff0c;选择“边框”&#xff0c;点击右下角有斜线的即可。 3、冻结窗口 一般冻结首列或首行&#xff0c;当我们翻页的时候&#xff0c;也能看到每一行的描述。 4、快捷键 1、 Ctrl1 设置单元格格…

【Java基础知识总结 | 第十篇】HashSet底层实现原理

文章目录 10.HashSet底层实现原理10.1HashSet特点10.2HashSet源码10.3 add流程10.4总结 10.HashSet底层实现原理 10.1HashSet特点 存储对象&#xff1a;HashSet 存储对象采用哈希表的方式&#xff0c;它不允许重复元素&#xff0c;即集合中不会包含相同的元素。当向 HashSet …

C语言实现快速排序算法

1. 什么是快速排序算法 快速排序的核心思想是通过分治法&#xff08;Divide and Conquer&#xff09;来实现排序。 算法的基本步骤是: 1. 选择一个基准值&#xff08;通常是数组中的某个元素&#xff09;&#xff0c;将数组分成两部分&#xff0c;使得左边的部分所有元素都小于…

2024.4.1-[作业记录]-day06-认识 CSS(三大特性、引入方式)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; day06-认识 CSS(三大特性、引入方式) 文章目录 day06-认识 CSS(三大特性、引入方式)作业…

xss.pwnfunction-Ma Spaghet!

根据代码得知 这个是根据get传参的并且是由someboby来接收参数的 所以 <script>alert(1137)</script> js并没有执行因为 HTML5中指定不执行由innerHTML插入的<script>标签 所以 ?somebody<img%20src1%20onerror"alert(1337)"> 这样就成…

Java栈和队列的实现

目录 一.栈(Stack) 1.1栈的概念 1.2栈的实现及模拟 二.队列(Queue) 2.1队列的概念 2.2队列的实现及模拟 2.3循环队列 2.4双端队列&#xff08;Deque&#xff09; 一.栈(Stack) 1.1栈的概念 栈:一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作…

JavaWeb--JavaScript Part 01

1. JavaScript概述 JavaScript&#xff08;简称JS&#xff09;是一种轻量级的、解释执行的客户端脚本语言&#xff0c;主要用于增强网页的交互性和动态性。它起源于Netscape的LiveScript&#xff0c;并在1995年发布时更名为JavaScript。尽管名称中包含"Java"&#xf…

JS 利用 webcam访问摄像头 上传到服务器

webcam JS 较为详细的指南 定义标题 <!doctype html> <html> <head><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>How to capture picture from webcam with Webcam.js</title></…

FreeMarker系列--指令的用法(全面,有示例)

原文网址&#xff1a;FreeMarker系列--指令的用法(全面&#xff0c;有示例)_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍FreeMark指令的用法。 相关网址 中文官方参考手册 assign 描述 使用该指令你可以创建一个新的变量&#xff0c; 或者替换一个已经存在的变量。注…

Redis实现高可用持久化与性能管理

前言 在生产环境中&#xff0c;为了实现Redis的高可用性&#xff0c;可以采用持久化、主从复制、哨兵模式和 Cluster集群的方法确保数据的持久性和可靠性。这里首先介绍一下使用持久化实现服务器的高可用。 目录 一、Redis 高可用方法 1. 持久化 2. 主从复制 3. 哨兵 4.…

2024.4.5-[作业记录]-day10-CSS 布局模型(层模型)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 作业 2024.4.5-学习笔记1 CSS定位1.1 相对定位 relative1.2 绝对定位 absolut…

【C++】map set 底层刨析

文章目录 1. 红黑树的迭代器2. 改造红黑树3. map 的模拟实现4. set 的模拟实现 在 C STL 库中&#xff0c;map 与 set 的底层为红黑树&#xff0c;那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。 1. 红黑树的迭代器 迭代器的好处是可以方便遍历&…