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

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_ii=1naixi 是 g 的倍数。

推论:正整数 a1 到 an 的最大公约数是 1 的充分必要条件是存在 n 个整数 x1 到 xn 满足 ∑i=1nai∗xi=1\sum_{i=1}^{n} a_i * x_i = 1i=1naixi=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 + log⁡m\log mlogm),其中n表示数组 nums 长度,m 表示与最大公约数 g 迭代次数最长的数字,其中求单次最大公约数的时间复杂度为 O(log⁡m\log mlogm),两个数求最大公约数,其中最大公约数 g 自增不减,总的求最大公约数所需时间为O(log⁡m\log mlogm),所以总的所需时间O(n + log⁡m\log mlogm)
  • 空间复杂度:O(1),不需要额外申请空间

相关文章:

Leetcode-每日一题1250. 检查「好数组」(裴蜀定理)

题目链接&#xff1a;https://leetcode.cn/problems/check-if-it-is-a-good-array/description/ 思路 方法&#xff1a;数论 题目意思很简单&#xff0c;让你在数组 nums中选取一些子集&#xff0c;可以不连续&#xff0c;子集中的每个数再乘以任意的数的和是否为1&#xff…...

OpenStack手动分布式部署环境准备【Queens版】

目录 1.基础环境准备&#xff08;两个节点都需要部署&#xff09; 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的使用

⭐️前言⭐️ 本篇文章就进入了自动化测试的章节了&#xff0c;如果作为一名测试开发人员&#xff0c;非常需要掌握自动化测试的能力&#xff0c;因为它不仅能减少人力的消耗&#xff0c;还能提升测试的效率。 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f…...

虚拟交换单元技术

支持VSU&#xff08;Virtual Switch Unit&#xff09;即虚拟交换单元技术。通过聚合链路连接&#xff0c;将多台物理设备虚拟为一台逻辑上统一的设备&#xff0c;使其能够实现统一的运行&#xff0c;利用单一IP 地址、单一Telnet 进程、单一命令行接口(CLI)、自动版本检查、自动…...

【STM32笔记】HAL库外部定时器、系统定时器阻塞、非阻塞延时

【STM32笔记】HAL库外部定时器、系统定时器阻塞、非阻塞延时 外部定时器 采用定时器做延时使用时 需要计算好分频和计数 另外还要配置为不进行自动重载 对于50MHz的工作频率 分频为50-1也就是50M/501M 一次计数为1us 分频为50000-1也就是1k 一次计数为1ms 我配置的是TIM6 只…...

[Springboot 单元测试笔记] - Mock 和 spy的使用

Springboot单元测试 - 依赖类mock测试 通常单元测试中&#xff0c;我们会隔离依赖对于测试类的影响&#xff0c;也就是假设所有依赖的一定会输出理想结果&#xff0c;在测试中可以通过Mock方法来确保输出结果&#xff0c;这也就引入另一个测试框架Mockito。 Mockito框架的作用…...

互联网新时代要来了(二)什么是AIGC?

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

75V的TVS二极管有哪些型号?常用的

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

测试开发之Django实战示例 第十章 创建在线教育平台

第十章 创建在线教育平台在上一章&#xff0c;我们为电商网站项目添加了国际化功能&#xff0c;还创建了优惠码和商品推荐系统。在本章&#xff0c;会建立一个新的项目&#xff1a;一个在线教育平台&#xff0c;并创内容管理系统CMS&#xff08;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管理系统发掘老客户的新增长点&#xff1f; 一直做投放拉新&#xff0c;很快营销成本会难以支撑&#xff0c;如果在私域运营中始终留不下老用户&#xff0c;那么运营也是失败的。 开发老客户的成本只需新客户成本的1/6&#xff0c;但很多企业对老客户都忽视了&…...

我用python疯狂爬取公司数据

我是半路从一个纯小白学过来的&#xff0c;学习途中也掉过许多坑&#xff0c;在这里建议新手要先把基础打扎实&#xff0c;然后再去学习自己需要的内容&#xff0c;不要想着全部学完再用&#xff0c;那样你是永远学不完的&#xff0c;用哪方面就学习哪方面的内容&#xff0c;不…...

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 &#xff0c;更没用过 jupyter &#xff0c;因此我的 python知识仅限于知道有 python 这么个编程语言&#xff0c;会写个 print("Hello World!!!") 而已&#xff0c;完全没听过 jupyter &#xff0c;因为某些原因今天需要安装下 jupyter 看看&am…...

k8s简单搭建

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

计算机SCI期刊审稿人,一般关注论文的那些问题? - 易智编译EaseEditing

编辑主要关心&#xff1a; &#xff08;1&#xff09;文章内容是否具有足够的创新性&#xff1f; &#xff08;2&#xff09;文章主题是否符合期刊的受众读者&#xff1f; &#xff08;3&#xff09;文章方法学是否合理&#xff0c;数据处理是否充分&#xff1f; &#xff08;…...

Docker迁移以及环境变量问题

问题一描述将docker容器通过docker export命令打包&#xff0c;传输到另外的服务器&#xff0c;再通过docker import命令导入后&#xff0c;发现原来docker容器中的环境变量失效了。解决方案1. 【无效方案】直接在docker容器中通过export命令设置环境变量。export LD_LIBRARY_P…...

Sphinx文档生成工具(二)

rst语法 官方的语法手册 行内的样式&#xff1a; #斜体 *message* #粗体 **message** #等宽 不能有换行 message标题 一级标题 ^^^^^^^^ 二级标题 --------- 三级标题 >>>>>>>>> 四级标题 ::::::::: 五级标题六级标题 """"…...

Python快速上手系列--JSON--入门篇

本章我们来看看json的一些应用。简单易懂还实用。一起来看看数据类型以及一些语法规则吧1、数字&#xff08;整数或浮点数&#xff09; 如&#xff1a;{"age":18, "score":70.5} 注意&#xff0c;数字直接写&#xff0c;不需要带任何符号2、字符串&#xf…...

axios中的GET POST PUT PATCH,发送请求时params和data的区别

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

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...