Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)
题目链接:https://leetcode.cn/problems/check-if-it-is-a-good-array/description/
思路
方法:数论
题目意思很简单,让你在数组 nums中选取一些子集,可以不连续,子集中的每个数再乘以任意的数的和是否为1,是则原数组就是个「好数组」
关键词:每个数相乘任意一个数相加
,数论里「裴蜀定理」是一个关于最大公约数的定理。也是拥有类似的推导(具体证明可参考「裴蜀定理」OI Wiki)。
「裴(pei)蜀定理」:设 a,b 是不全为零的整数,则存在整数 x,y, 使得 ax+by= gcd(a,b).
「裴蜀定理」同样也可以推广到多个整数的情况。对于全不为 0 的任意 n 个整数 a1, a2, a3, a4 … an,记这 n 个整数的最大公约数为 0,则对于任意 n 个整数 x1, x2, x3, x4 … xn都满足 ∑i=1nai∗xi\sum_{i=1}^{n} a_i * x_i∑i=1nai∗xi 是 g 的倍数。
推论:正整数 a1 到 an 的最大公约数是 1 的充分必要条件是存在 n 个整数 x1 到 xn 满足 ∑i=1nai∗xi=1\sum_{i=1}^{n} a_i * x_i = 1∑i=1nai∗xi=1
回到原题,我们判断数组 nums 是否是个「好数组」。由「裴蜀定理」推导 0 < i < n,题目等价于求 nums 中的全部数字的最大公约数是否等于 1,若等于 1 则原数组为「好数组」,否则不是。
如何求数组 nums 的 最大公约数 g,初始化 g = nums[0],遍历数组,更新 g = gcd(g, nums[i]),遍历完全部数字后,g 即为数组 nums 中全部的元素的最大公约数。然后判断其是否等于 1 即可。在实现过程中我们也可以进一步做优化:如果遍历过程中出现最大公约数等于 1 的情况,则由于 1 和任何正整数的最大公约数都是 1,此时可以提前结束遍历。
代码示例
func isGoodArray(nums []int) bool {// 有数据为[1]的情况if len(nums) == 1 && nums[0] == 1{return true}g := nums[0]for i := 1; i < len(nums); i++ {g = gcd(g, nums[i])if g == 1 {return true}}return false
}func gcd(a, b int) int {if a % b == 0 {return b}return gcd(b, a % b)
}
复杂度分析
- 时间复杂度:O(n + logm\log mlogm),其中n表示数组 nums 长度,m 表示与最大公约数 g 迭代次数最长的数字,其中求单次最大公约数的时间复杂度为 O(logm\log mlogm),两个数求最大公约数,其中最大公约数 g 自增不减,总的求最大公约数所需时间为O(logm\log mlogm),所以总的所需时间O(n + logm\log mlogm)
- 空间复杂度:O(1),不需要额外申请空间
相关文章:

Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)
题目链接:https://leetcode.cn/problems/check-if-it-is-a-good-array/description/ 思路 方法:数论 题目意思很简单,让你在数组 nums中选取一些子集,可以不连续,子集中的每个数再乘以任意的数的和是否为1ÿ…...

OpenStack手动分布式部署环境准备【Queens版】
目录 1.基础环境准备(两个节点都需要部署) 1.1关闭防火墙 1.2关闭selinux 1.3修改主机名 1.4安装ntp时间服务器 1.5修改域名解析 1.6添加yum源 2.数据库安装配置 2.1安装数据库 2.2修改数据库 2.3重启数据库 2.4初始化数据库 3.安装RabbitMq…...

Web自动化测试——selenium的使用
⭐️前言⭐️ 本篇文章就进入了自动化测试的章节了,如果作为一名测试开发人员,非常需要掌握自动化测试的能力,因为它不仅能减少人力的消耗,还能提升测试的效率。 🍉欢迎点赞 👍 收藏 ⭐留言评论 …...
虚拟交换单元技术
支持VSU(Virtual Switch Unit)即虚拟交换单元技术。通过聚合链路连接,将多台物理设备虚拟为一台逻辑上统一的设备,使其能够实现统一的运行,利用单一IP 地址、单一Telnet 进程、单一命令行接口(CLI)、自动版本检查、自动…...

【STM32笔记】HAL库外部定时器、系统定时器阻塞、非阻塞延时
【STM32笔记】HAL库外部定时器、系统定时器阻塞、非阻塞延时 外部定时器 采用定时器做延时使用时 需要计算好分频和计数 另外还要配置为不进行自动重载 对于50MHz的工作频率 分频为50-1也就是50M/501M 一次计数为1us 分频为50000-1也就是1k 一次计数为1ms 我配置的是TIM6 只…...
[Springboot 单元测试笔记] - Mock 和 spy的使用
Springboot单元测试 - 依赖类mock测试 通常单元测试中,我们会隔离依赖对于测试类的影响,也就是假设所有依赖的一定会输出理想结果,在测试中可以通过Mock方法来确保输出结果,这也就引入另一个测试框架Mockito。 Mockito框架的作用…...

互联网新时代要来了(二)什么是AIGC?
什么是AIGC? 最近,又火了一个词“**AIGC”**2022年被称为是AIGC元年。那么我们敬请期待,AIGC为我们迎接人工智能的下一个时代。 TIPS:内容来自百度百科、知乎、腾讯、《AIGC白皮书》等网页 什么是AIGC?1.什么是AIGC?…...

75V的TVS二极管有哪些型号?常用的
瞬态抑制TVS二极管工作峰值反向电压最低3.3V,最高可达513V,甚至更高。很多电子工程师都知道,TVS二极管在实际应用选型过程中,第一步要确认的就是其工作峰值反向电压。2023年春节已过,东沃电子正月初八就开工了…...

测试开发之Django实战示例 第十章 创建在线教育平台
第十章 创建在线教育平台在上一章,我们为电商网站项目添加了国际化功能,还创建了优惠码和商品推荐系统。在本章,会建立一个新的项目:一个在线教育平台,并创内容管理系统CMS(Content Management System&…...

Hadoop高可用搭建(二)
目录 解压Hadoop 改名 更改配置文件 workers hdfs-site.xml core-site.xml hadoop-env.sh mapred-site.xml yarn-site.xml 设置环境变量 启动集群 启动zk集群 启动journalnode服务 格式化hfds namenode 启动namenode 同步namenode信息 查看namenode节点状态 …...
如何用企微SCRM管理系统发掘老客户的新增长点?
如何用企微SCRM管理系统发掘老客户的新增长点? 一直做投放拉新,很快营销成本会难以支撑,如果在私域运营中始终留不下老用户,那么运营也是失败的。 开发老客户的成本只需新客户成本的1/6,但很多企业对老客户都忽视了&…...

我用python疯狂爬取公司数据
我是半路从一个纯小白学过来的,学习途中也掉过许多坑,在这里建议新手要先把基础打扎实,然后再去学习自己需要的内容,不要想着全部学完再用,那样你是永远学不完的,用哪方面就学习哪方面的内容,不…...
EMR集群运行TPC-DS在云盘和OSS中的对比
1.简介 TPC-DS是大数据领域最为知名的Benchmark标准。本文介绍使用阿里云EMR集群运行TPC-DS在云盘和OSS中的表现对比。 2.环境准备 1.创建EEMR-5.10.1集群 1个master,2个core,3台机器都s是4c16g。 2.安装Git和Maven sudo yum install -y git maven3.下载TPC-DS Benchmark工…...

菜鸟在 windows 下 python 中安装 jupyter 踩坑要点 、被神化的 VsCode
我平时用不到 python ,更没用过 jupyter ,因此我的 python知识仅限于知道有 python 这么个编程语言,会写个 print("Hello World!!!") 而已,完全没听过 jupyter ,因为某些原因今天需要安装下 jupyter 看看&am…...

k8s简单搭建
前言 最近学习k8s,跟着网上各种教程搭建了简单的版本,一个master节点,两个node节点,这里记录下防止以后忘记。 具体步骤 准备环境 用Oracle VM VirtualBox虚拟机软件安装3台虚拟机,一台master节点,两台…...

计算机SCI期刊审稿人,一般关注论文的那些问题? - 易智编译EaseEditing
编辑主要关心: (1)文章内容是否具有足够的创新性? (2)文章主题是否符合期刊的受众读者? (3)文章方法学是否合理,数据处理是否充分? (…...
Docker迁移以及环境变量问题
问题一描述将docker容器通过docker export命令打包,传输到另外的服务器,再通过docker import命令导入后,发现原来docker容器中的环境变量失效了。解决方案1. 【无效方案】直接在docker容器中通过export命令设置环境变量。export LD_LIBRARY_P…...

Sphinx文档生成工具(二)
rst语法 官方的语法手册 行内的样式: #斜体 *message* #粗体 **message** #等宽 不能有换行 message标题 一级标题 ^^^^^^^^ 二级标题 --------- 三级标题 >>>>>>>>> 四级标题 ::::::::: 五级标题六级标题 """"…...
Python快速上手系列--JSON--入门篇
本章我们来看看json的一些应用。简单易懂还实用。一起来看看数据类型以及一些语法规则吧1、数字(整数或浮点数) 如:{"age":18, "score":70.5} 注意,数字直接写,不需要带任何符号2、字符串…...

axios中的GET POST PUT PATCH,发送请求时params和data的区别
axios 中 get/post请求方式 1. 前言 最近突然发现post请求可以使用params方式传值,然后想总结一下其中的用法。 2.1 分类 经过查阅资料,get请求是可以通过body传输数据的,但是许多工具类并不支持此功能。 在postman中,选择get请…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...