【数据结构与算法 | 灵神题单 | 分治(链表)篇】力扣148

1. 力扣148:排序链表

1.1 题目:

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

示例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

1.2 思路:

使用堆,每次取出来的数就是最小的。但进阶是想让我们用分治来解决链表的排序问题。

1.3 题解:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {// 优先队列PriorityQueue<Integer> pq = new PriorityQueue<>();ListNode p = head;while(p != null){pq.offer(p.val);p = p.next;}ListNode dummy = new ListNode(-1, null);p = head;while(!pq.isEmpty()){p.val = pq.poll();p = p.next;}return head;}
}

2. 力扣23:合并K个升序链表

2.1 题目:

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

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

示例 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

2.2 思路:

2.3 题解:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) {return null;}PriorityQueue<Integer> pq = new PriorityQueue<>();for (int i = 0; i < lists.length; i++) {ListNode p = lists[i];ListNode q = p;while(q != null) {pq.offer(q.val);q = q.next;}}ListNode dummy = new ListNode(0);ListNode q = dummy;while (! pq.isEmpty()) {ListNode p = new ListNode(pq.poll());q.next = p;p.next = null;q = p;}return dummy.next;}
}

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

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

相关文章

Unity程序基础框架

概述 单例模式基类 没有继承 MonoBehaviour 继承了 MonoBehaviour 的两种单例模式的写法 缓存池模块 &#xff08;确实挺有用&#xff09; using System.Collections; using System.Collections.Generic; using UnityEngine;/// <summary> /// 缓存池模块 /// 知识点 //…

C++STL~~stackqueue

文章目录 容器适配器一、stack&queue的概念二、stack&queue的使用三、stack&queue的练习四、总结 容器适配器 什么是适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)&#xff0c;该种模式是将一个类…

Leetcode 移动零

要求将数组中的所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。下面是该题的 C 解决方案&#xff1a; class Solution { public:void moveZeroes(vector<int>& nums) {int nonZeroPos 0; // 记录非零元素应该放置的位置// 遍历数组&#xff0c;…

【北京迅为】《STM32MP157开发板使用手册》- 第三十章Cortex-M4通用定时器实验

iTOP-STM32MP157开发板采用ST推出的双核cortex-A7单核cortex-M4异构处理器&#xff0c;既可用Linux、又可以用于STM32单片机开发。开发板采用核心板底板结构&#xff0c;主频650M、1G内存、8G存储&#xff0c;核心板采用工业级板对板连接器&#xff0c;高可靠&#xff0c;牢固耐…

相图的科学应用,陶瓷材料创新

陶瓷材料因其优异的物理和化学性能&#xff0c;在航空航天、电子、生物医学等多个领域展现出广阔的应用前景。陶瓷材料的性能很大程度上取决于其微观结构&#xff0c;包括晶粒大小、相组成和分布。相图作为描述陶瓷材料在不同条件下的相变行为和相平衡关系的图表反映了陶瓷材料…

Element-ui el-table 全局表格排序

实现效果如下&#xff1a; 一、当页数据排序 如果只想要当前页面排序&#xff0c;只会涉及到前端&#xff0c;只需在<el-table-column>标签上添加 :sortable"true"即可 二、自定义排序 如果想要全局排序&#xff0c;需要自定义排序函数&#xff0c;请求后台排…

Springboot项目打war包运行及错误解决

一,打war包 1. 修改pom.xml 为了不影响原pom.xml, 我复制了一个文件叫pom_war.xml , 需要打war包就采用pom_war.xml进行打war包, 你也可以直接修改pom.xml ① 打包方式改为war 没有就增加此配置 <packaging>war</packaging> ② 排除内嵌tomcat依赖 <de…

怎样在备忘录中添加提醒?怎么设置备忘录提醒

备忘录作为我们日常生活中常用的软件&#xff0c;其记录事项的便捷性已经得到了广泛认可。无论是工作计划、购物清单还是个人日记&#xff0c;备忘录都能帮助我们将这些信息快速记录下来。然而&#xff0c;如果备忘录能够进一步提供提醒功能&#xff0c;那么它将变得更加实用&a…

122.rk3399 uboot(2017.09) 源码分析2-initf_dm(2024-09-09)

这里接着上一篇来吧&#xff1a; https://blog.csdn.net/zhaozhi0810/article/details/141927053 本文主要是dm_init_and_scan函数的分析&#xff0c;这个内容比较复杂&#xff0c;我也是第一次阅读&#xff0c;错误之处在所难免&#xff0c;请多指教。 uboot的dm框架需要了解…

MyBatis 面试题11-27

11、Mybatis 是如何将 sql 执行结果封装为目标对象并返回的? 都有哪些映射形式&#xff1f; Mybatis 在执行 SQL 查询后&#xff0c;会将结果集封装为目标对象并返回。这主要依赖于 Mybatis 的映射机制&#xff0c;它提供了两种主要的映射形式&#xff1a; 第一种&#xff1…

代码质量护航:结合Checkstyle、SpringBoot与Git的最佳实践

在团队开发中&#xff0c;保持一致的代码风格和高质量的代码至关重要。为了提升团队的整体代码质量&#xff0c;防止低质量代码的提交&#xff0c;使用工具对代码进行自动化检查是非常有效的手段之一。在这篇博客中&#xff0c;我将介绍如何通过结合 Checkstyle、Spring Boot 和…

Zotero使用(一)PDF文件导入不会自动识别

上面两种&#xff0c;一种中文&#xff0c;一种英文&#xff0c;会发现&#xff0c;中文的导入进去之后不会自动识别&#xff0c;部分英文也是。不能自动识别就会缺少导出参考文献的功能&#xff0c;怎么办&#xff1f; 发现之前导入喜欢使用PDF格式 可以结合.ris格式&#xf…

网络安全 day5 --- 反弹SHELL不回显带外正反向连接防火墙出入站文件下载

免责声明 本免责声明适用于作者所有文章内容。使用者需明确&#xff0c;网络安全技术仅供学习和合法研究使用&#xff0c;不得用于任何非法活动&#xff0c;如未经授权的入侵、攻击或数据窃取&#xff0c;所有相关法律责任由使用者自行承担。由于网络安全操作可能带来系统崩溃、…

Linux_kernel驱动开发11

一、改回nfs方式挂载根文件系统 在产品将要上线之前&#xff0c;需要制作不同类型格式的根文件系统 在产品研发阶段&#xff0c;我们还是需要使用nfs的方式挂载根文件系统 优点&#xff1a;可以直接在上位机中修改文件系统内容&#xff0c;延长EMMC的寿命 【1】重启上位机nfs服…

【计算机网络】HTTPHTTPS

HTTP&HTTPS HTTP协议初识HTTP如何抓包Fiddler的使用抓包查看包的信息 报文格式请求报文响应报文报文对比 URLHTTP方法认识Header初识状态码 HTTPS协议为什么需要 HTTPS加密基础知识HTTPS的工作流程引入对称加密引入非对称加密引入证书HTTPS 的工作流程 浏览器从输入URL到展…

短视频剪辑从简单到复杂,这四款很OK!

作为一个刚刚踏入视频剪辑世界的新手&#xff0c;我最近可是忙得不亦乐乎。我尝试了四款流行的视频剪辑软件&#xff0c;今天&#xff0c;就让我来和大家分享一下我的使用感受&#xff0c;看看哪款软件更适合我们这些初学者。这里先说一句&#xff0c;选择视频剪辑软件就像挑衣…

opencv学习:calcHist 函数绘制图像直方图及代码实现

cv2.calcHist 函数是 OpenCV 库中用于计算图像直方图的函数。直方图是一种统计图像中像素值分布的工具&#xff0c;它可以提供图像的亮度、颜色等信息。这个函数可以用于灰度图像和彩色图像。 函数语法 hist cv2.calcHist(images, channels, mask, histSize, ranges, accumu…

解决 PyCharm 无法启动 Jupyter 服务器的问题:报错分析与解决方案

文章目录 报错背景报错详细信息解决方案pycharm 设置 报错背景 在使用 pycharm 付费版的过程中&#xff0c;发现一直无法启动 jupyter 服务器。 一直也不知道是为什么&#xff0c;直到在终端输入&#xff1a; jupyter notebook发现 jupyter 服务无法启动。 报错详细信息 下…

数据库系列之GaussDB数据库中逻辑对象关系简析

初次接触openGauss或GaussDB数据库的逻辑对象&#xff0c;被其中的表空间、数据库、schema和用户之间的关系&#xff0c;以及授权管理困惑住了&#xff0c;与熟悉的MySQL数据库的逻辑对象又有明显的不同。本文旨在简要梳理下GaussDB数据库逻辑对象之间的关系&#xff0c;以加深…

浅谈EXT2文件系统(1)

简介 EXT2&#xff08;Second Extended Filesystem&#xff09;文件系统是Linux操作系统的早期文件系统之一&#xff0c;它于 1993 年推出&#xff0c;是第一个旨在克服 Ext 文件系统限制的商业文件系统。EXT2 没有日志功能&#xff0c;EXT2 支持的单个文件大小为 2TB&#xf…