【数据结构与算法 | 灵神题单 | 插入链表篇】力扣2807, LCR 029, 147

1. 力扣2807:在链表中插入最大公约数

1.1 题目:

你一个链表的头 head ,每个结点包含一个整数值。

在相邻结点之间,请你插入一个新的结点,结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

示例 1:

输入:head = [18,6,10,3]
输出:[18,6,6,2,10,1,3]
解释:第一幅图是一开始的链表,第二幅图是插入新结点后的图(蓝色结点为新插入结点)。
- 18 和 6 的最大公约数为 6 ,插入第一和第二个结点之间。
- 6 和 10 的最大公约数为 2 ,插入第二和第三个结点之间。
- 10 和 3 的最大公约数为 1 ,插入第三和第四个结点之间。
所有相邻结点之间都插入完毕,返回链表。

示例 2:

输入:head = [7]
输出:[7]
解释:第一幅图是一开始的链表,第二幅图是插入新结点后的图(蓝色结点为新插入结点)。
没有相邻结点,所以返回初始链表。

提示:

  • 链表中结点数目在 [1, 5000] 之间。
  • 1 <= Node.val <= 1000

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 insertGreatestCommonDivisors(ListNode head) {if(head == null || head.next == null){return head;}ListNode dummy = new ListNode(10086, head);ListNode cur = dummy;// 用来求最大公约数while(cur.next != null && cur.next.next != null){int a = cur.next.val;int b = cur.next.next.val;int max = Integer.max(a, b);int min = Integer.min(a, b);// 如果可以整除,最小值就是最大公约数if(max % min == 0){} else {// 更相减损术int sub = max - min;while(sub != min){max = Integer.max(sub, min);min = Integer.min(sub, min);sub = max - min;}}ListNode p = new ListNode(min, cur.next.next);cur.next.next = p;// 这里是p的原因在于:我们要处理的是cur的下一个节点和下下一个节点// 而p此时位于的节点刚好在要处理的两个节点前面cur = p;}return dummy.next;}
}

2. 力扣LCR:029:循环有序列表的插入

2.1 题目:

给定循环单调非递减列表中的一个点,写一个函数向这个列表中插入一个新元素 insertVal ,使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针,并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置,可以选择任意一个位置插入新的值,插入后整个列表仍然保持有序。

如果列表为空(给定的节点是 null),需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1:

输入:head = [3,4,1], insertVal = 2
输出:[3,4,1,2]
解释:在上图中,有一个包含三个元素的循环有序列表,你获得值为 3 的节点的指针,我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间,插入之后,整个列表如上图所示,最后返回节点 3 。

示例 2:

输入:head = [], insertVal = 1
输出:[1]
解释:列表为空(给定的节点是 null),创建一个循环有序列表并返回这个节点。

示例 3:

输入:head = [1], insertVal = 0
输出:[1,0]

提示

  • 0 <= Number of Nodes <= 5 * 10^4
  • -10^6 <= Node.val <= 10^6
  • -10^6 <= insertVal <= 10^6

2.2 思路:

先遍历链表找到链表中最新的最大值节点,该节点的next节点即该链表的最小值节点(可能会有很多个最小值节点,但该最小值节点是边界)。

从最小值节点开始遍历,碰到合适的位置就可以插入,然后返回head即可。如果直到遍历完链表,仍然找不到位置插入,该需要插入节点的值比整个链表的值都要大或都要小,则需要插入到最小值节点的后面,这个时候我们就可以想到找到该最小值节点的上一个节点,parent节点跟踪最小值节点min_point。然后处理parent节点和要插入节点的关系即可。

2.3 题解:

/*
// Definition for a Node.
class Node {public int val;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _next) {val = _val;next = _next;}
};
*/class Solution {public Node insert(Node head, int insertVal) {Node insert = new Node(insertVal);// 如果链表为空,需要特殊判断if(head == null){insert.next = insert;return insert;}// 遍历链表找到最小值节点// 发现最新的最大值的后面就是最小值// 因为最大值可能有很多个,我们要最新的,所以p.val >= max有等于号int max = head.val;Node max_point = head;Node p = head.next;// n表示链表的长度int n = 1;while(p != head){if(p.val >= max){max = p.val;max_point = p;}n++;p = p.next;}// max_point指向了最大值的节点Node min_point = max_point.next;Node parent = null;while(n-- > 0){// 找到合适的地方就插入if(min_point.val <= insertVal && insertVal <= min_point.next.val){insert.next = min_point.next;min_point.next = insert;return head;}parent = min_point;min_point = min_point.next;}// 还没插入成功,插到最小值后面insert.next = parent.next;parent.next = insert;return head;}
}

3. 力扣147:对链表进行插入排序

3.1 题目:

给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

  1. 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  2. 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。

对链表进行插入排序。

示例 1:

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

示例 2:

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

提示:

  • 列表中的节点数在 [1, 5000]范围内
  • -5000 <= Node.val <= 5000

3.2 思路:

由于个人实力太菜,写着一跑就超时了,无奈转换成求解数组的插入排序。

3.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 insertionSortList(ListNode head) {// 特殊情况直接返回if(head == null || head.next == null) {return head;}ListNode node = head;int n = 0;while(node != null){n++;node = node.next;}int[] arr = new int[n];node = head;n = 0;while(node != null){arr[n++] = node.val;node = node.next;}for(int i = 1; i < arr.length; i++){int t = arr[i];int j = i - 1;while(j >= 0 && t < arr[j]){arr[j+1] = arr[j];j--;}if(j != i - 1){arr[j+1] = t;}}node = head;int k = 0;while(node != null){node.val = arr[k++];node = node.next;}return head;}
}

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

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

相关文章

大数据新视界 --大数据大厂之Flink强势崛起:大数据新视界的璀璨明珠

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

【网络安全】服务基础第二阶段——第四节:Linux系统管理基础----Linux网络与日志服务器

目录 一、Linux基础知识 1.1 Linux系统常用目录及命令 1.1.1 常用目录 1.1.2 常用命令 1.1.3 Linux系统文件和命令 1.1.3 文件操作 1.1.4 文件打包和压缩 1.1.5 Linux系统包管理 1.1.6 RPM命令 二、YUM 2.1 YUM 2.1.1 YUM工具 2.1.2 YUM配置 2.2 YUM源安装前置准…

机器人的静力分析与动力学

参考链接&#xff1a;4-13刚体的惯性张量_哔哩哔哩_bilibili4-13刚体的惯性张量, 视频播放量 6540、弹幕量 2、点赞数 79、投硬币枚数 38、收藏人数 145、转发人数 23, 视频作者 每一天都应不同, 作者简介 ROS1是DCS,ROS2是FCS&#xff0c;相关视频&#xff1a;机器人动力学拉格…

(八) 初入MySQL 【主从复制】

案例概况 在企业应用中&#xff0c;成熟的业务通常数据量都比较大 单台MySQL在安全性、 高可用性和高并发方面都无法满足实际的需求 &#xff0c;所以需要配置多台主从数据库服务器以实现读写分离来满足需求 一、主从复制原理 1.1、 MySQL的复制类型 基于语句的复制(STATEME…

从0开始的算法(数据结构和算法)基础(十一)

回溯算法 什么是回溯算法 回溯算法&#xff0c;根据字面意思来理解这个算法是将每一步的操作可以进行回溯&#xff0c;实际上是对这个每一步的操作进行记录&#xff0c;确保可以返回上一步的操作&#xff0c;可能是对回溯操作之前的做一个复现&#xff0c;也有可能是可操作的回…

神经网络中的那些浮点数

模型进行需要大量显存和算力进行支持&#xff0c;精度越高需要的内存和算力也越多&#xff0c;本文将介绍在模型中使用的不同类型的浮点数。 FP32 (Float32)&#xff1a; • 精度和稳定性&#xff1a;FP32 提供 23 位尾数和 8 位指数的高精度 • 性能&#xff1a;尽管 FP32 是通…

学习大数据DAY56 业务理解和第一次接入

作业1 1 了解行业名词 ERP CRM OA MES WMS RPA SAAS 了解每个系统的功能和应用 ERP 系统&#xff0c;&#xff08;Enterprise Resource Planning&#xff0c;企业资源计划系统&#xff09;&#xff1a;ERP 系统 是一种用于管理企业各类资源的软件系统&#xff0c;包括生产管理…

极狐GitLab CI/CD 作业一直处于等待状态,如何解决?

本分分享 GitLab CI/CD Job 不工作的的故障排查方法&#xff1a;当 GitLab Runner 不接受 Job&#xff0c;Job 一直处于等待状态&#xff0c;如何解决此问题。 极狐GitLab 为 GitLab 在中国的发行版&#xff0c;中文版本对中国用户更友好。极狐GitLab 支持一键私有化部署&…

【Hot100】LeetCode—72. 编辑距离

目录 1- 思路题目识别动规五部曲 2- 实现⭐72. 编辑距离——题解思路 3- ACM 实现 原题链接&#xff1a;72. 编辑距离 1- 思路 题目识别 识别1 &#xff1a;两个字符串之间相互转换&#xff0c;增、删、替换 最少的操作次数 动规五部曲 1- 定义 dp 数组 dp[i][j] 代表&…

如何增加Google收录量?

想增加Google收录量&#xff0c;首先自然是你的页面数量就要多&#xff0c;但这些页面的内容也绝对不能敷衍&#xff0c;你的网站都没多少页面&#xff0c;谷歌哪怕想收录都没办法&#xff0c;当然&#xff0c;这是一个过程&#xff0c;持续缓慢的增加页面&#xff0c;增加网站…

11.5.软件系统分析与设计-面向对象的程序设计与实现

面向对象的程序设计与实现 设计模式 Java代码 C代码

神经网络案例实践之单层感知器求解-学习篇

二维线性分类问题 单层感知器作为线性分类器被广泛应用 问题分析&#xff1a; 首先给了五个输入样本&#xff0c;输入样本和位置信息如下所示&#xff0c;现在要学习一个模型&#xff0c;在二维空间中把两个样本分开&#xff0c;输入数据是个矩阵&#xff0c;矩阵中有五个样本…

手写排班日历

手写排班日历&#xff1a; 效果图&#xff1a; vue代码如下&#xff1a; <template><div class"YSPB"><div class"title">排班日历</div><div class"banner"><span classiconfont icon-youjiantou click&qu…

jmeter设置全局token

1、创建setup线程&#xff0c;获取token的接口在所有线程中优先执行&#xff0c;确保后续线程可以拿到token 2、添加配置原件-Http信息头管理器&#xff0c;添加取样器-http请求 配置好接口路径&#xff0c;端口&#xff0c;前端传参数据&#xff0c;调试一下&#xff0c;保证获…

影刀RPA实战:自动化同步商品库存至各大电商平台(二)

在当今的电商世界中&#xff0c;多平台运营已成为常态。商家需要在多个电商平台上维护商品库存的一致性&#xff0c;以确保顾客体验的流畅性和库存管理的高效性。运营人员每天面临的问题&#xff0c;就是把公司的商品库存数据&#xff0c;间断性的同步到电商平台上&#xff0c;…

简单比较 http https http2,我们要如何把http升级为https

&#x1f9d1;‍&#x1f4bb; 写在开头 点赞 收藏 学会&#x1f923;&#x1f923;&#x1f923; 什么是HTTP 超文本传输​​协议&#xff08;HTTP&#xff09;是用于传输诸如HTML的超媒体文档的应用层协议。它被设计用于Web浏览器和Web服务器之间的通信&#xff0c;但它也…

C# 通过拖控件移动窗体

目录 引言一、通过控件事件移动窗体1、创建窗体界面2、添加控件事件3、添加代码 二、通过windowsAPI移动窗体1、 构建窗体和添加事件2、代码展示 三、其它方式 引言 在C#Form窗体设计中&#xff0c;如果我们不需要使用默认边框设计自己个性化的窗体&#xff08;FromBorderStyl…

2.关于Cloud各种组件的停更/升级/替换

目前主流的cloud组件 备注&#xff1a;黑色部分是springcloud社区原版&#xff0c;红色的是SpringCloud Alibaba。 服务注册与发现 Consul Alibaba Nacos 服务调用和负载均衡 LoadBalancer OpenFeign 分布式事务 Alibaba Seata 服务熔断和降级 Circuit Breaker Alibaba Sentine…

Golang使用ReverseProxy实现反向代理

目录 1.源码结构体 2.官方单机示例 3.使用示例 4.简单的http服务&#xff08;用于测试&#xff09; 1.源码结构体 type ReverseProxy struct {// Rewrite 必须是一个函数&#xff0c;用于将请求修改为要使用 Transport 发送的新请求。然后&#xff0c;其响应将原封不动地…

微软数据库的SQL注入漏洞解析——Microsoft Access、SQLServer与SQL注入防御

说明:本文仅是用于学习分析自己搭建的SQL漏洞内容和原理,请勿用在非法途径上,违者后果自负,与笔者无关;本文开始前请认真详细学习《‌中华人民共和国网络安全法》‌及其相关法规内容【学法时习之丨网络安全在身边一图了解网络安全法_中央网络安全和信息化委员会办公室】 。…