当前位置: 首页 > news >正文

leetcode.在链表中插入最大公约数

文章目录

  • 题目
  • 解题方法
  • 复杂度
  • Code

Problem: 2807. 在链表中插入最大公约数

题目

给你一个链表的头 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

解题方法

写一个计算最大公约数的函数,使用辗转相除法计算,当b为0时候,说明上一次调用gcd的时候 a%b=0,b就已经是a的最大公约数了,我们用a保存了上一次调用的b的值,所以a就是我们最终的答案

辗转相除法的证明过程,这个老师讲的很好 :

https://www.bilibili.com/video/BV1my4y1z7Zn/?spm_id_from=333.337.search-card.all.click&vd_source=f4b0f39061295153d69abcbac1aaa3e6

在插入节点的时候需要判断当前节点和下一个节点是否存在,存在则直接插入即可

复杂度

时间复杂度:

O ( n ) O(n) O(n)

空间复杂度:

O ( 1 ) O(1) O(1)

Code


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:def gcd1(a,b):if b==0:return aa,b = b,a%breturn gcd1(a,b)p = headwhile p and p.next:val = gcd1( p.val , p.next.val) node = ListNode(val,p.next)p.next = nodep = p.next.nextreturn head

相关文章:

leetcode.在链表中插入最大公约数

文章目录 题目解题方法复杂度Code Problem: 2807. 在链表中插入最大公约数 题目 给你一个链表的头 head &#xff0c;每个结点包含一个整数值。 在相邻结点之间&#xff0c;请你插入一个新的结点&#xff0c;结点值为这两个相邻结点值的 最大公约数 。 请你返回插入之后的链表。…...

云原生学习系列之基础环境准备(单节点安装kubernetes)

一、环境要求 操作系统CentOS 7.x-86_x64 硬件配置&#xff1a;内存2GB或2G&#xff0c;CPU 2核或CPU 2核&#xff0c;需要在虚拟机中提前设置好&#xff0c;不然后续会报错 二、系统初始化 1、设置主机名 # 在master节点执行 hostnamectl set-hostname master01 2、配置主…...

【数据结构】二叉树的概念及堆

前言 我们已经学过了顺序表、链表、栈和队列这些属于线性结构的数据结构&#xff0c;那么下面我们就要学习我们第一个非线性结构&#xff0c;非线性结构又有哪些值得我们使用的呢&#xff1f;那么接下来我们就将谈谈树的概念了。 1.树的概念与结构 1.1树的概念 树是一种非线性…...

美年大健康黄伟:从选型到迁移,一个月升级核心数据库

核心生产系统的数据库&#xff0c;从接到替换需求到完成分布式升级&#xff0c;需要多久&#xff1f;一个月&#xff0c;这是美年大健康的回答。一个月集中调配各种资源&#xff0c;美年大健康完成了应用程序基本零改造的平滑迁移&#xff0c;新数据库在成本更低的前提下&#…...

OpenHarmony应用构建工具Hvigor的构建流程

前言 OpenHarmony 应用和服务使用 Hvigor 作为工程的构建工具。本篇文章将介绍 Hvigor 的构建流程&#xff0c;通过修改脚本配置使 Hvigor 执行自定义任务。 Hvigor 的构建流程 加载命令行参数和环境变量&#xff1b;初始化项目结构&#xff0c;创建 Project 和 Module 实例…...

ChatGPT在金融财务领域的10种应用方法

1.生成报告 在金融领域中&#xff0c;最耗时的任务之一是报告生成。通过ChatGPT&#xff0c;您可以在一定程度上自动化这个过程。这款人工智能工具可以获取关于公司财务表现的结构化数据&#xff0c;并生成一份书面摘要&#xff0c;详细说明关键点、趋势和观察结果。这个功能在…...

全程云OA ajax.ashx SQL注入漏洞复现

0x01 产品简介 全程云OA为企业提供日常办公管理、公文管理、工作请示、汇报、档案、知识体系、预算控制等26个功能,超过100多个子模块。为企业内部提供高效、畅通的信息渠道,同时也能大力推动公司信息系统发展,提高企业的办公自动化程度和综合管理水平,加快企业信息的流通…...

VMware 安装 macOS虚拟机(附工具包)

VMware 安装 macOS虚拟机&#xff0c;在Windows上体验苹果macOS系统&#xff01; 安装教程&#xff1a;VMware 安装 macOS虚拟机VMware Workstation Pro 是一款强大的虚拟机软件&#xff0c;可让您在 Windows 电脑上运行 macOS 系统。只需简单几步操作&#xff0c;即可轻松安装…...

Tomcat与Servlet是什么关系

Tomcat与Servlet是什么关系 Apache Tomcat和Servlet之间存在密切的关系&#xff0c;可以说它们是一对密切合作的组件。下面是它们的关系&#xff1a; Tomcat是Servlet容器&#xff1a; Tomcat是一个开源的、轻量级的Servlet容器。Servlet容器是一个Web服务器扩展&#xff0c;用…...

C++11_右值引用

文章目录 前言一、右值引用是什么&#xff1f;那么&#xff0c;什么又是右值&#xff1f;右值引用 二、使用步骤和意义1.1.11.2 2.右值引用的最大意义2.1 完美转发2.2 万能折叠 前言 C11 是2011年对C这门语言发布的新标准&#xff0c;并且此次标准引入了十分多的新特性&#x…...

C#使用条件语句判断用户登录身份

目录 一、示例 二、生成 利用条件语句判断用户登录身份&#xff0c;根据用户登录身份的不同&#xff0c;给予相应的操作权限。 一、示例 主要用if语句及ComboBox控件。其中&#xff0c;ComboBox是窗体中的下拉列表控件&#xff0c;在使用ComboBox控件前&#xff0c;可以先向…...

在VM下使用Composer完成快照方式的软件制作

Composer允许您构建软件、应用程序、偏好设置文件或是文档的安装包&#xff0c;安装包可以部署到远程电脑或是作为镜像流程的一部分。构建软件包的第一步就是创建包源&#xff0c;根据要打包的软件&#xff0c;Composer允许您监视软件的安装和使用驱动器上已存在的文件来创建包…...

YOLOv5改进 | Neck篇 | 利用Damo-YOLO的RepGFPN改进特征融合层

一、本文介绍 本文给大家带来的改进机制是Damo-YOLO的RepGFPN(重参数化泛化特征金字塔网络),利用其优化YOLOv5的Neck部分,可以在不影响计算量的同时大幅度涨点(亲测在小目标和大目标检测的数据集上效果均表现良好涨点幅度超级高!)。RepGFPN不同于以往提出的改进模块,其…...

设计模式——最全梳理,最好理解

新年献礼&#xff01; 设计模式呕心梳理 创建型模式 单例模式&#xff08;Singleton Pattern&#xff09;https://blog.csdn.net/qq_34869143/article/details/134874044 整理中... 结构型模式 代理模式&#xff08;Proxy Pattern&#xff09;https://blog.csdn.net/qq_34…...

外包干了4个月,技术退步明显了...

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01; 而我已经在一个企业干了四…...

rust 注释文档生成 cargo doc

rust的cargo文档生成 只需要在每个函数写清楚注释&#xff0c;就可以自动生成文档&#xff0c;很方便 即不用写文档&#xff0c;又可以快速查看&#xff0c;是开发rust的必备技能 rust安装和开发环境配置&#xff0c;可以参考&#xff1a;链接 1.写注释的方法 连续三个 \ 即…...

大语言模型(LLM)框架及微调 (Fine Tuning)

大语言模型&#xff08;LLM&#xff09; 技术作为人工智能领域的一项重要创 新在今年引起了广泛的关注。 LLM 是利用深度学习和大数据训练的人工智能系统&#xff0c;专门 设计来理解、生成和回应自然语言。这些模型通过分析大量 的文本数据来学习语言的结构和用法&#xff0c;…...

速盾高防ip:专业防御ddos

速盾高防IP是速盾网络为企业提供的专业DDoS攻击防御解决方案之一。作为一种先进的网络安全服务&#xff0c;速盾高防IP致力于保护客户的网络资源免受分布式拒绝服务&#xff08;DDoS&#xff09;攻击的威胁。以下是速盾高防IP的一些关键特点和优势&#xff1a; 实时攻击监测&am…...

第5章-第8节-Java面向对象中的内部类

1、内部类&#xff1a;属于类的成员之一&#xff0c;类的内部又定义类&#xff0c;外层的class称为外部类&#xff0c;内部的class称为内部类。 设计了某个类&#xff0c;根据需求发现其内部又需要定义一个独立的内部结构&#xff0c;此时就考虑将其定义为内部类&#xff0c;内…...

首次引入大模型!Bert-vits2-Extra中文特化版40秒素材复刻巫师3叶奈法

Bert-vits2项目又更新了&#xff0c;更新了一个新的分支&#xff1a;中文特化&#xff0c;所谓中文特化&#xff0c;即针对中文音色的特殊优化版本&#xff0c;纯中文底模效果百尺竿头更进一步&#xff0c;同时首次引入了大模型&#xff0c;使用国产IDEA-CCNL/Erlangshen-Megat…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...