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

LeetCode 2807. 在链表中插入最大公约数【链表,迭代,递归】1279

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

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

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

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

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

示例 1:

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

示例 2:

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

提示:

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

解法 迭代

遍历链表,在当前节点 cur \textit{cur} cur 后面插入 g c d gcd gcd 节点,同时 gcd \textit{gcd} gcd 节点指向 cur \textit{cur} cur 的下一个节点。插入后, cur \textit{cur} cur 更新为 cur . next . next \textit{cur}.\textit{next}.\textit{next} cur.next.next ,也就是 c u r cur cur 原来的下一个节点,开始下一轮循环。循环直到 c u r cur cur 没有下一个节点为止。

// cpp
class Solution {
public:ListNode* insertGreatestCommonDivisors(ListNode* head) {for (auto cur = head; cur->next; cur = cur->next->next)cur->next = new ListNode(gcd(cur->val, cur->next->val), cur->next);return head;}
};
// java
class Solution {public ListNode insertGreatestCommonDivisors(ListNode head) {for (ListNode cur = head; cur.next != null; cur = cur.next.next) {cur.next = new ListNode(gcd(cur.val, cur.next.val), cur.next);}return head;}private int gcd(int a, int b) { while (a != 0) {int t = a;a = b % a;b = t;}return b;}
}
// python
class Solution:def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:cur = headwhile cur.next:cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)cur = cur.next.nextreturn head
// go
/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func insertGreatestCommonDivisors(head *ListNode) *ListNode {for cur := head; cur.Next != nil; cur = cur.Next.Next {cur.Next = &ListNode{gcd(cur.Val, cur.Next.Val), cur.Next}}return head
}
func gcd(a, b int) int {for a != 0 {a, b = b % a, a}return b
}
// rust
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {let mut cur = &mut head;while cur.as_ref().unwrap().next.is_some() {let x = cur.as_mut().unwrap();let next = x.next.take();x.next = Some(Box::new(ListNode {val: Self::gcd(x.val, next.as_ref().unwrap().val),next,}));cur = &mut cur.as_mut().unwrap().next.as_mut().unwrap().next;}head}fn gcd(mut a: i32, mut b: i32) -> i32 {while a != 0 {(a, b) = (b % a, a);}b}
}

复杂度分析:

  • 时间复杂度: O ( n log ⁡ ⁡ U ) \mathcal{O}(n\log⁡U) O(nlogU) ,其中 n n n 为链表长度, U U U 为节点值的最大值。每次计算 g c d gcd gcd 需要 O ( log ⁡ ⁡ U ) \mathcal{O}(\log⁡U) O(logU) 的时间。
  • 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1) 。返回值的空间不计入。

相关文章:

LeetCode 2807. 在链表中插入最大公约数【链表,迭代,递归】1279

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

Hive之set参数大全-3

D 是否启用本地任务调试模式 hive.debug.localtask 是 Apache Hive 中的一个配置参数&#xff0c;用于控制是否启用本地任务调试模式。在调试模式下&#xff0c;Hive 将尝试在本地模式下运行一些任务&#xff0c;以便更容易调试和分析问题。 具体来说&#xff0c;当 hive.de…...

Golang拼接字符串性能对比

g o l a n g golang golang的 s t r i n g string string类型是不可修改的&#xff0c;对于拼接字符串来说&#xff0c;本质上还是创建一个新的对象将数据放进去。主要有以下几种拼接方式 拼接方式介绍 1.使用 s t r i n g string string自带的运算符 ans ans s2. 使用…...

【问题解决】web页面html锚点定位后内容被遮挡问题解决【暗锚】

正常的锚点跳转 a标签的href填写目标元素的id即可 <a href"#my_target">to div1</a> <div id"my_target">div1</div> 内容被顶栏遮挡示例 但是当id所在元素被嵌套多层flex和relative布局之后&#xff0c;跳转后部分内容会被遮挡…...

easyui datagrid无数据时显示无数据

这里写自定义目录标题 需求解决办法 需求 使用datagrid显示记录时&#xff0c;结果查询记录数为0&#xff0c;此时需要显示无数据。 示例代码 <table id"dg"></table>$(#dg).datagrid({url:datagrid_data.json,columns:[[{field:code,title:Code,widt…...

动态规划python简单例子-斐波那契数列

def fibonacci(n):dp [0, 1] [0] * (n - 1) # 初始化动态规划数组for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2] # 计算斐波那契数列的第 i 项print(dp)return dp[n] # 返回斐波那契数列的第 n 项# 示例用法 n 10 # 计算斐波那契数列的第 10 项 result fibonac…...

免 费 搭 建 多模式商城:b2b2c、o2o、直播带货一网打尽

鸿鹄云商 b2b2c产品概述 【b2b2c平台】&#xff0c;以传统电商行业为基石&#xff0c;鸿鹄云商支持“商家入驻平台自营”多运营模式&#xff0c;积极打造“全新市场&#xff0c;全新 模式”企业级b2b2c电商平台&#xff0c;致力干助力各行/互联网创业腾飞并获取更多的收益。从消…...

Python AttributeError: ‘NoneType‘ object has no attribute ‘shape‘如何解决

Python AttributeError: ‘NoneType‘ object has no attribute ‘shape‘ 运行出现上述错误&#xff0c;这个错误表示某个图像对象为 NoneType &#xff0c;没有 shape 属性。通常情况下&#xff0c;这是因为 OpenCV 没有能够正确地加载图像&#xff0c;导致无法访问图像数据。…...

vue3自定义确认密码匹配验证规则

// 自定义确认密码匹配验证规则 const matchPassword (rules:any, value:any, callback:any) > {if (value ! addData.payPwd) {callback(new Error(两次密码输入不一致&#xff01;))} else {callback()} }const rules reactive({payPwd: [{ required: true, message: &q…...

岗位所处定位,岗位职责

电子产品所需岗位&#xff1a;pcb设计电路板,fpga&#xff0c;嵌入式&#xff0c;应用层&#xff08;前后端&#xff0c;移动端&#xff09;。 PCB 岗位职责&#xff1a;1.负责器件.工程或者项目与技术验证类的PCB板设计工作&#xff1b;2.协助项目中部分模块的PCB&#xff08…...

2024阿里云服务器配置推荐方案

阿里云服务器配置怎么选择合适&#xff1f;CPU内存、公网带宽和ECS实例规格怎么选择合适&#xff1f;阿里云服务器网aliyunfuwuqi.com建议根据实际使用场景选择&#xff0c;例如企业网站后台、自建数据库、企业OA、ERP等办公系统、线下IDC直接映射、高性能计算和大游戏并发&…...

OceanBase原生分布式数据库

1.历史背景 在Java Web项目中&#xff0c;常常使用免费开源的MySQL数据库存储业务数据&#xff0c;按业界经验MySQL单库超过多大数据体量&#xff0c;或单表超过几百万条数据后就会出现查询变慢的情况&#xff0c;单实例数据库只能扩展物理资源(CPU、内存)&#xff0c;来提升查…...

首次使用go-admin

go-admin 1.1 拉取 拉去后端代码 git clone https://github.com/go-admin-team/go-admin.git拉取前端代码 git clone gitgithub.com:go-admin-team/go-admin-ui.git 1.2 编译 cd ./go-admingo mod tidygo build1.3 配置文件的修改 这里可以可以根据自己的需要进行自定义两…...

软件工程概论---内聚性和耦合性

目录 一.耦合性 1.内容耦合 2.公共耦合 4.控制耦合 5.标记耦合&#xff08;特征耦合&#xff09; 6.数据耦合 7.非直接耦合 二.内聚性 1.偶然内聚 2.逻辑内聚 3.时间内聚 4.过程内聚 5.通信内聚 6.顺序内聚 7.功能内聚 一.耦合性 耦合性是指软件结构中模块相互…...

纯血鸿蒙「扩圈」100天,酝酿已久的突围

坦白讲&#xff0c;去年参加华为开发者大会看到HarmonyOS NEXT&#xff08;仅运行鸿蒙原生应用&#xff0c;所以也称作「纯血鸿蒙」&#xff09;的时候&#xff0c;小雷也没料想到鸿蒙原生应用生态的发展速度会如此之快。 9月25日&#xff0c;华为正式对外宣布启动HarmonyOS NE…...

UICollection Compositional Layout全详解

本文字数&#xff1a;8325字 预计阅读时间&#xff1a;45分钟 01 Collection View Layout全详解 UICollectionView在iOS中是构建复杂布局的强大工具。iOS13中引入的 UICollectionViewCompositionalLayout为创建自定义布局提供了全新的可能性。本文将深入探讨Compositional Lay…...

单例模式的模板

参考了网上的一些单例模式&#xff0c;自己也写一个模板。 要点&#xff1a; 线程安全性单例对象的唯一性 #include <mutex> //在模板类 Singleton 中&#xff0c;可以定义单例模式的实现细节 template <typename T> class Singleton { public://通过删除拷贝构造…...

C#基础-空处理

在c#中&#xff0c;值对象是没有办法赋值为null的。比如说&#xff0c;你想要定义一个布尔值&#xff0c;你的赋值数据要么得是true、要么就得是false&#xff0c;默认情况下我们永远没可能给这个布尔赋值为null&#xff0c;即使只是对这个变量进行声明而不初始化数据&#xff…...

测试平台开发vue组件化重构前端代码

基于 springbootvue 的测试平台开发 继续更新&#xff08;人在魔都 T_T&#xff09;。 这期其实并不是一个详细的开发过程记录&#xff0c;主要还是针对本次前端重构来聊聊几个关注点。 目前重构的总进度在80%&#xff0c;重构完的页面没什么变化&#xff0c;再回顾一下。 一…...

龍运当头--html做一个中国火龙祝大家龙年大吉

🐉效果展示 🐉HTML展示 <body> <!-- partial:index.partial.html --> <svg><defs><g id=...

Dockerfile语法和简单镜像构建

Dockerfile是一个用于定义Docker镜像的文本文件&#xff0c;包含了一系列的指令和参数&#xff0c;用于指示Docker在构建镜像时应该执行哪些操作&#xff0c;例如基于哪个基础镜像、复制哪些文件到镜像中、运行哪些命令等。 Dockerfile文件的内容主要有几个部分组成&#xff0c…...

uniapp使用wxml-to-canvas开发小程序保存canvas图片

微信小程序官方解决方案&#xff1a;wxml-to-canvas 使用wxml-to-canvas要知道一些前提条件 1、只能画view&#xff0c;text&#xff0c;image 2、每个元素必须要设置宽高 3、默认是flex布局&#xff0c;可以通过flexDirection: "column"来改变排列方式 4、文字 必…...

关于数据库切换的麻烦

背景介绍 现项目使用了两个数据源&#xff0c;分别为A、B&#xff0c;两个数据库的数据结构并不相同&#xff0c;数据库A是用来做查询一些基本信息的&#xff0c;数据库B是用来保留业务操作数据的。后端是在mapper层用DS注解来区分哪些地方用数据库A&#xff0c;而哪些地方用数…...

Qt/QML编程学习之心得:Linux下读写文件File(24)

在Linux嵌入式系统中,经常会使用Qt来读写一个文件,判断一个文件是否存在,具体如何实现呢? 首先,要使用linux系统中相关的头文件: #include <unistd.h> #include <stdio.h> #include <stdlib.h> 其次,判断路径是否存在, if(!dir.exists()){mkdir(…...

【Vue2+3入门到实战】(22)VUE3之组合式API - setup、reactive和ref函数、computed、watch、生命周期函数详细讲解

目录 一、组合式API - setup选项1. setup选项的写法和执行时机2. setup中写代码的特点3. <script setup>语法糖 二、组合式API - reactive和ref函数1. reactive2. ref3. reactive 对比 ref 三、组合式API - computed四、组合式API - watch1. 侦听单个数据2. 侦听多个数据…...

如何在互联网上找到你想要的数据?

互联网时代&#xff0c;信息爆炸&#xff0c;怎么在网上查到到自己想要的信息已经变难了。毕竟经常搜索的内容前几页都是广告。 那么如何在大量的广告和垃圾信息中获取到自己想要的信息呢? 首先&#xff0c;明确自己的需求&#xff0c;比如你想找哪个方面的数据&#xff0c;…...

揭秘淘宝商品详情API如何助力电商创新发展

淘宝商品详情API是淘宝开放平台提供的一种数据接口服务&#xff0c;能够获取到淘宝网商品详情的各种信息&#xff0c;包括商品标题、价格、销量、评价等。通过淘宝商品详情API&#xff0c;开发者可以轻松地获取到这些数据&#xff0c;并利用这些数据进行商业分析和应用开发。 …...

vue element plus Space 间距

虽然我们拥有 Divider 组件&#xff0c;但很多时候我们需要不是一个被 Divider 组件 分割开的页面结构&#xff0c;因此我们会重复的使用很多的 Divider 组件&#xff0c;这在我们的开发效率上造成了一定的困扰。 间距组件就是为了解决这种困扰应运而生的。 基础用法# 最基础…...

【驱动序列】C#获取电脑硬件之CPU信息,以及它都有那些品牌

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是是《驱动序列》文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识…...

目标检测-One Stage-YOLO v3

文章目录 前言一、YOLO v3的网络结构和流程二、YOLO v3的创新点总结 前言 根据前文目标检测-One Stage-YOLOv2可以看出YOLOv2的速度和精度都有相当程度的提升&#xff0c;但是精度仍较低&#xff0c;YOLO v3基于一些先进的结构和思想对YOLO v2做了一些改进。 提示&#xff1a;…...