day20

第一题

23. 合并 K 个升序链表

        本题是已经知道有多个链表,需要我们将这些链表按照升序排列的规则组合到一起,同时这些链表都是升序排列的;

解法一:

        利用优先级队列

步骤一:利用优先级队列床架一个小根堆;

步骤二:将每一个链表的头结点放在小根堆里面;

步骤三:创建一个新节点,将第二不得堆顶的节点插入到新节点后面,同时将该节点所在的链表的后一个节点放在小根堆里面开始进行下一个循环;

        细节:当小根堆的堆顶不为空时,一直要进行出栈操作;每一个链表的当前节点的下一个节点不为空,就会一直进行入堆操作;

综上分析,代码如下:

class Solution {public ListNode mergeKLists(ListNode[] lists) {//1、创建一个小根堆PriorityQueue <ListNode> heap = new PriorityQueue<>((v1,v2) -> v1.val - v2.val);//2、把所有的头结点放在小根堆中for(ListNode head : lists){if(head != null){heap.offer(head);}}//3、依次上堆顶的进入链表,合并链表ListNode ret = new ListNode(0);ListNode prev = ret;while(!heap.isEmpty()){ListNode t = heap.poll();prev.next = t;prev = t;if(t.next != null) heap.offer(t.next);}return ret.next;}
}

解法二:使用分支-递归的思想

        

        如上图是六个链表,我们采用分支的思想,分成两的部分,左部分和右部分,就这样一直分,直到被分的链表为一个或两个,我们就进行合并,将两个链表按照升序的规则一一合并,这样由小和大,慢慢的同一层级别的链表再次合并,这样,我们最后返回的链表就是这几个链表合并之后的升序大链表;

        综上所述,代码如下:

class Solution {public ListNode mergeKLists(ListNode[] lists) {return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists,int left,int right ){if(left > right) return null;if(left == right) return lists[left];//1、平分数组int mid = (left + right )/2;//[left,mid],[mid+1,right]//2、递归处理左右两个部分ListNode l1 = merge(lists,left,mid);ListNode l2 = merge(lists,mid+1,right);//3、合并两个有序链表return mergeTwoList(l1,l2);}public ListNode mergeTwoList(ListNode l1,ListNode l2){if(l1 == null) return l2;if(l2 == null) return l1;//合并两个有序链表ListNode head = new ListNode(0);ListNode cur1 = l1,cur2 = l2,prev = head;while(cur1 != null && cur2 != null){if(cur1.val <= cur2.val){prev.next = cur1;prev = cur1;cur1 = cur1.next;}else{prev.next = cur2;prev = cur2;cur2 = cur2.next;}}if(cur1 != null) prev.next = cur1;if(cur2 != null) prev.next = cur2;return head.next;}
}

第二题

25. K 个一组翻转链表

本题采用模拟的方法来解决:

 步骤一:

        遍历整个链表,求出整个链表的长度,计算出我们要逆序的链表为n组,且有多少个节点不需要遍历;

步骤二:

        采用头插法,来插入n组长度为k的链表;

        细节一:使用cur来指向原链表的头结点,即即将要插入的节点,用prev指针表示新链表指向被查位置的前一个节点

        

        采用头插法插入:

        首先定义指针next来指向下一个要插入的原链表的节点;

        操作如上,插入完成后,next指针和cur指针分别向后移动一位;

        重复上述操作,直到完成第一组的插入操作:

细节二:

        此时我们定义一个tmp指针,指向每一组链表的第一个节点,当每一组链表被逆转之后,就将prev指针指向tmp指针,确保我们我们要插入的元素从prev指针开始逆转;

就这样,一直操作完n组,到了不需要逆转的几个节点组成的最后链表,直接添加即可;

        故此,代码如下

class Solution {public ListNode reverseKGroup(ListNode head, int k) {//1、需要逆序的有几个组int n = 0;ListNode cur = head;while(cur != null){cur = cur.next;n++;}n /= k;//2、重复n次,长度为k的链表逆序操作ListNode newHead = new ListNode(0);ListNode prev = newHead;cur = head;for(int i = 0;i < n;i++){ListNode tmp = cur;for(int j = 0;j < k; j++){//开始头插ListNode next = cur.next;cur.next = prev.next;prev.next = cur;cur = next;}prev = tmp;}prev.next = cur;return newHead.next;}
}

ps:本次的内容就到这里了,如果对你有所帮助的话,就请一键三连哦!!!

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

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

相关文章

事务报错没有显示回滚导致DDL阻塞引发的问题

在业务开发过程中&#xff0c;显示的开启事务并且在事务处理过程中对不同的情况进行显示的COMMIT或ROLLBACK&#xff0c;这是一个完整数据库事务处理的闭环过程。 这种在应用开发逻辑层面去handle的事务执行的结果&#xff0c;既确保了事务操作的数据完整性&#xff0c;又遵循了…

Jenkins流水线pipeline--基于上一章的工作流程

1流水线部署 1.流水线文本名Jenkinsfile,将流水线放入gitlab远程仓库代码里面 2构建参数 2pipeline脚本 Jenkinsfile文件内容 pipeline {agent anyenvironment {key"value"}stages {stage("拉取git仓库代码") {steps {deleteDir()checkout scmGit(branc…

kafka-生产者发送消息消费者消费消息

文章目录 1、生产者发送消息&消费者消费消息1.1、获取 kafka-console-producer.sh 的帮助信息1.2、生产者发送消息到某个主题1.3、消费主题数据 1、生产者发送消息&消费者消费消息 1.1、获取 kafka-console-producer.sh 的帮助信息 [rootlocalhost ~]# kafka-console…

CISCN 2022 初赛 ez_usb

还是从第一个 URB向后看 发现 同时 存在 2.8.1 2.10.1 2.4.1 但是显然 2.4.1 是7个字节 不满足 usb流量要求 只考虑 2.8.1 和 2.10.1 tshark -r ez_usb.pcapng -T json -Y "usb.src \"2.8.1\"" -e usbhid.data > 281.json 正常取数据即可 import js…

Vue3 - Mac系统用文本编辑写html不显示效果的坑

平时在win系统下&#xff0c;可以直接对文本进行编辑&#xff0c;非常的舒服。 在mac系统中&#xff0c;也有类似的功能&#xff0c;就是文本编辑&#xff0c;没想到居然还有坑。 这是我mac系统中创建的html文件&#xff0c;想着没有几行代码&#xff0c;就没有开编辑器了&am…

crossover软件是干什么的 crossover软件安装使用教程 crossover软件如何使用

CrossOver 以其出色的跨平台兼容性&#xff0c;让用户在Mac设备上轻松运行各种Windows软件&#xff0c;无需复杂的设置或额外的配置&#xff0c;支持多种语言&#xff0c;满足不同国家和地区用户的需求。 CrossOver 软件是干嘛的 使用CrossOver 不必购买Windows 授权&#xf…

Java Spring Boot 从必应爬取图片

获取图片主要就是通过必应图片页面控制台的元素&#xff0c;确认图片和标题在哪个类中&#xff08;浏览器 F12&#xff09; 引入依赖 这里需要引入两个依赖 jsoup 和 hutool maven依赖网站地址&#xff1a;Maven Repository: Search/Browse/Explore (mvnrepository.com) 挑选…

基于java18多端展示+ idea hbuilder+ mysql家政预约上门服务系统,源码交付,支持二次开发

基于java18多端展示 idea hbuilder mysql家政预约上门服务系统&#xff0c;源码交付&#xff0c;支持二次开发 家政预约上门系统是一种通过互联网或移动应用平台&#xff0c;为用户提供在线预约、下单、支付和评价家政服务的系统。该系统整合了家政服务资源&#xff0c;使用户能…

c++学生管理系统

想要实现的功能 1&#xff0c;可以增加学生的信息&#xff0c;包括&#xff08;姓名&#xff0c;学号,c成绩&#xff0c;高数成绩&#xff0c;英语成绩&#xff09; 2&#xff0c;可以删除学生信息 3&#xff0c;修改学生信息 4&#xff0c;显示所有学生信息 5&#xff0c…

图形学初识--多边形剪裁算法

文章目录 前言正文为什么需要多边形剪裁算法&#xff1f;前置知识二维直线直线方程&#xff1a;距离本质&#xff1a;点和直线距离关系&#xff1a; 三维平面平面方程距离本质&#xff1a;点和直线距离关系&#xff1a; Suntherland hodgman算法基本介绍基本思想二维举例问题描…

uni-app解决表格uni-table样式问题

一、如何让表格文字只显示一行&#xff0c;超出部分用省略号表示 步骤 &#xff1a; 给table设置table-layout:fixed; 列宽由表格宽度和列宽度设定。&#xff08;默认是由单元格内容设定&#xff09;让表格元素继承父元素宽度固定table-layout: inherit;overflow: hidden;超过…

Docker安装启动Mysql

1、安装Docker&#xff08;省略&#xff09; 网上教程很多 2、下载Mysql5.7版本 docker pull mysql:5.7 3、查看镜像是够下载成功 docker images 4、启动镜像&#xff0c;生成容器 docker run --name mysql5.7 -p 13306:3306 -e MYSQL_ROOT_PASSWORD123456 -d mysql:5.7 5…

我成功创建了一个Electron应用程序

1.创建electron项目命令&#xff1a; yarn create quick-start/electron electron-memo 2选择&#xff1a;√ Select a framework: vue √ Add TypeScript? ... No √ Add Electron updater plugin? ... Yes √ Enable Electron download mirror proxy? ... Yes 3.命令&a…

services层和controller层

services层 我的理解&#xff0c;services层是编写逻辑代码语句最多的一个层&#xff0c;非常重要&#xff0c;在实际的项目中&#xff0c;负责调用Dao层中的mybatis&#xff0c;在我的项目中它调用的是这两个文件 举例代码如下 package com.example.sfdeliverysystem.servic…

基于单片机的 wifi 家电开关控制系统设计

摘要 : 本文是利用 51 单片机基础知识结合 wifi 通信技术完成的一套可通过手机无线遥控家电开关系统设计。整个系统以 STC89C51 单片机为核心&#xff0c;采用业界主流的 ESP8266wifi 模块作为通信模块&#xff0c;家电开关的自动控制部分采用 3 路继电器开关来实现。本系统的…

【python】多线程(3)queue队列之不同延时时长的参数调用问题

链接1&#xff1a;【python】多线程&#xff08;笔记&#xff09;&#xff08;1&#xff09; 链接2&#xff1a;【python】多线程&#xff08;笔记&#xff09;&#xff08;2&#xff09;Queue队列 0.问题描述 两个线程&#xff0c;但是不同延时时长&#xff0c;导致数据输出…

MyBatis框架-开发方式+参数传递+#{}、${}+返回值处理+查询结果封装为对象+resultType

一、开发方式 MyBatis-Dao层Mapper接口化开发 二、注意事项 1、Mapper接口与Mapper.xml映射文件要满足4个对应 &#xff08;1&#xff09;Mapper接口的全类名必须与Mapper映射文件中的namespace相同 &#xff08;2&#xff09;Mapper接口中的每一个方法名在Mapper映射文件…

961题库 北航计算机 操作系统 附答案 选择题形式

有题目和答案&#xff0c;没有解析&#xff0c;不懂的题问大模型即可&#xff0c;无偿分享。 第1组 习题 计算机系统的组成包括&#xff08; &#xff09; A、程序和数据 B、处理器和内存 C、计算机硬件和计算机软件 D、处理器、存储器和外围设备 财务软件是一种&#xff…

iOS——类与对象底层探索

类和对象的本质 当我们使用OC创建一个testClass类并在main函数创建它的实例对象的时候&#xff0c;OC的底层到底是什么样的呢&#xff1f; 首先&#xff0c;我们要了解OC对象的底层结构&#xff0c;那么我们就得知道&#xff1a;OC本质底层实现转化其实都是C/C代码。 使用下面…

11Linux学习笔记

Linux 实操篇 目录 文章目录 Linux 实操篇1.rtm包&#xff08;软件&#xff09;1.1 基本命令1.2 基本格式1.3安装rtm包1.4卸载rtm包 2.apt包2.1 基本命令结构2.2 常用选项2.3常用命令 1.rtm包&#xff08;软件&#xff09; 1.1 基本命令 1.2 基本格式 1.3安装rtm包 1.4卸载r…