【合并 K 个升序链表】python刷题记录

R4-分治篇

目录

最小堆方法

分治法

ps:

如果只是数组就很好处理了

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:stack=[]for row in lists:for r in row:stack.append(r)stack.sort()return stack

最小堆方法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#堆可以比较节点大小
ListNode.__lt__=lambda a,b : a.val<b.val
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:#cur是指针,随时合并下一个节点。#dummy是哨兵,dummy.next返回最终的链表#h是最小堆cur = dummy =ListNode()#所有头节点入堆h=[head for head in lists if head]#堆化(前提是堆能比较节点大小)heapify(h)while h:node=heappop(h)if node.next:heappush(h,node.next)cur.next=nodecur=cur.nextreturn dummy.next

 

分治法

灵神题解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#堆可以比较节点大小
ListNode.__lt__=lambda a,b : a.val<b.val
class Solution:#合并两个有序链表def mergeTwoLists(self,list1,list2):cur = dummy =ListNode()while list1 and list2:if list1.val<list2.val:cur.next=list1list1=list1.nextelse:cur.next=list2list2=list2.nextcur=cur.next#拼接剩余链表cur.next=list1 if list1 else list2return dummy.next#本题合并所有升序链表def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:m=len(lists)if m==0:return Noneif m==1:return lists[0]left=self.mergeKLists(lists[:m//2])right=self.mergeKLists(lists[m//2:])return self.mergeTwoLists(left,right)

牛啊

ps:

今天get到堆的出堆等基本操作方法

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring AOP 源码剖析

一.AOP基础概念 切面&#xff08;Aspect&#xff09;&#xff1a;切面是跨越多个类的关注点模块化&#xff0c;如事务管理。切面由切点和通知组成。连接点&#xff08;Join Point&#xff09;&#xff1a;在程序执行过程中某个特定的点&#xff0c;如方法调用或异常抛出。在Sp…

kafka基础概念二

1.Kafka中主题和分区的概念 1.主题Topic 主题-topic在kafka中是一个逻辑的概念&#xff0c;kafka通过topic将消息进行分类。不同的topic会被订阅该topic的消费者消费 但是有一个问题&#xff0c;如果说这个topic中的消息非常非常多&#xff0c;多到需要几T来存&#xff0c;因…

区块链的搭建和运维4

区块链的搭建和运维4 (1) 搭建基于MySQL分布式存储的区块链 1.构建单群组网络节点 使用开发部署工具构建单群组网络节点&#xff0c;命令如下&#xff1a; bash build_chain.sh -l 127.0.0.1:4 -p 30300,20200,85452. 启动 MySQL 并设置账户密码 输入如下命令&#xff0c;…

关于Git使用不成功的问题解决方案记录

关于Git使用不成功的问题解决方案记录 前言代理连接不成功总结 前言 项目中建立了Git小仓库&#xff0c;但是在使用中出现了无法push新的代码&#xff0c;显示端口出现问题&#xff0c;发现网站和端口都没有问题&#xff0c;可以打开网站。但是还是连接失败&#xff0c;无法下…

MySQL笔记(十):MySQL管理

一、用户管理 #用户管理 -- 原因&#xff1a;当我们做项目开发时&#xff0c;可以根据不同的开发人员&#xff0c;赋给她相应的mysql操作权限。 -- 所以&#xff0c;mysql数据库管理人员&#xff08;root&#xff09;&#xff0c;根据需要创建不同的用户&#xff0c;赋给相应的…

android中打包apk体积优化方案

1.在配置文件AndroidManifest中新增 android:extractNativeLibs"true" 2.在模块build文件下配置支持的cpu,一般配置64的就行了,多配一种so库体积大一倍&#xff0c;择优。 ndk { abiFilters arm64-v8a } 3.在模块builde文件下配置混淆除去无用的资源文件 注:三种…

【Kubernetes】Deployment 的状态

Deployment 的状态 Deployment 控制器在整个生命周期中存在 3 3 3 种状态&#xff1a; 已完成&#xff08;Complete&#xff09;进行中&#xff08;Progressing&#xff09;失败&#xff08;Failed&#xff09; 通过观察 Deployment 的当前特征&#xff0c;可以判断 Deploym…

Win32注册表操作

注册表的概念 注册表是一个存储计算机配置信息的数据库&#xff0c;用于存储计算机上的硬件、安装的软件、系统设置以及用户账户配置等重要信息。对注册表的编辑不当可能会影响计算机的正常运行。应用程序可以调用API函数来对注册表进行增、删等操作。 注册表结构 运行Regedi…

Linux学习笔记:Linux基础知识汇总(个人复习版)

常用命令&#xff1a; 1、ls -a&#xff1a;显示所有文件&#xff08;包括隐藏文件&#xff09;&#xff0c;简洁版 -l&#xff1a;显示所有文件&#xff0c;详细版 -R&#xff1a;显示所有文件以及子目录下文件&#xff0c;简洁版 可以搭配使用。 2、netstat -i&#x…

priority_queue模拟实现【C++】

文章目录 全部的实现代码放在了文章末尾什么是适配器模式&#xff1f;准备工作包含头文件定义命名空间类的成员变量什么是仿函数&#xff1f;比较仿函数在priority_queue中的作用通过传入不同的仿函数可以做到大堆和小堆之间的切换通过传入不同的仿函数可以做到改变priority_qu…

书生.浦江大模型实战训练营——(三)Git基本操作与分支管理

最近在学习书生.浦江大模型实战训练营&#xff0c;所有课程都免费&#xff0c;以关卡的形式学习&#xff0c;也比较有意思&#xff0c;提供免费的算力实战&#xff0c;真的很不错&#xff08;无广&#xff09;&#xff01;欢迎大家一起学习&#xff0c;打开LLM探索大门&#xf…

Java设计模式(命令模式)

定义 将一个请求封装为一个对象&#xff0c;从而让你可以用不同的请求对客户进行参数化&#xff0c;对请求排队或者记录请求日志&#xff0c;以及支持可撤销的操作。 角色 抽象命令类&#xff08;Command&#xff09;&#xff1a;声明用于执行请求的execute方法&#xff0c;通…

LeNet5模型搭建

文章目录 LeNet1 搭建模型2 训练模型3 测试模型3.1 预测一3.2 预测二 LeNet LeNet 诞生于 1994 年&#xff0c;是最早的卷积神经网络之一&#xff0c;并且推动了深度学习领域的发展。自从 1988 年开始&#xff0c;在许多次成功的迭代后&#xff0c;这项由 Yann LeCun 完成的开拓…

【最长递增子序列】python刷题记录

R4-dp 目录 常规方法遇到以下序列时就会变得错误 动态规划的思路 单调栈 ps: class Solution:def lengthOfLIS(self, nums: List[int]) -> int:#最简单的方法nlen(nums)if n<2:return nmx1for i in range(n):max_i1for j in range(i1,n):if nums[i]<nums[j]:nums…

RK3568平台(触摸篇)FT5X06驱动程序分析

一.设备树 &i2c1 {status "okay";myft5x06: my-ft5x0638 {compatible "my-ft5x06";reg <0x38>;reset-gpios <&gpio0 RK_PB6 GPIO_ACTIVE_LOW>;interrupt-parent <&gpio3>;interrupts-gpio <&gpio3 RK_PA5 GPI…

大数据-70 Kafka 高级特性 物理存储 日志存储 日志清理: 日志删除与日志压缩

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff08;已更完&#xff09;HDFS&#xff08;已更完&#xff09;MapReduce&#xff08;已更完&am…

K8S资源之NameSpace

作用 隔离资源(默认不隔离网络) 查看所有的NS kubectl get ns创建NS kubectl create ns hello删除NS kubectl delete ns hello

VUE基础快速入门

VUE 和 VUE-Cli VUE 是一种流行的渐进式JavaScript框架&#xff0c;用于构建Web用户界面它具有易学、轻量级、灵活性强、高效率等特点&#xff0c;并且可以与其他库和项目集成是目前最流行的前端框架之一VUE-Cli 称为“VUE脚手架”,它是由VUE官方提供的客户端&#xff0c;专门为…

简单Qt贪吃蛇项目

目录 先看效果 项目介绍 界面一&#xff1a;游戏大厅界面 界面二&#xff1a;关卡选择界面​编辑 界面三&#xff1a;游戏界面 游戏大厅页面 游戏关卡选择页面 游戏房间页面 封装贪吃蛇数据结构 初始化游戏房间界面 设置窗口大小、标题、图标等 蛇的移动 初始化贪…

RocketMQ Dashboard安装

RocketMQ Dashboard 是一个基于 Web 的管理工具&#xff0c;用于监控和管理 RocketMQ 集群。它提供了一个用户友好的界面&#xff0c;使管理员能够轻松地查看和操作 RocketMQ 系统中的各种组件和状态。 主要功能包括&#xff1a; 集群管理: 监控和管理 NameServer 和 Broker …