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

Leetcode.1250 检查「好数组」

题目链接

Leetcode.1250 检查「好数组」 Rating : 1983

题目描述

给你一个正整数数组 nums,你需要从中任选一些子集,然后将子集中每一个数乘以一个 任意整数,并求出他们的和。

假如该和结果为 1,那么原数组就是一个「好数组」,则返回 True;否则请返回 False

示例 1:

输入:nums = [12,5,7,23]
输出:true
解释:挑选数字 5 和 7。
53 + 7(-2) = 1

示例 2:

输入:nums = [29,6,10]
输出:true
解释:挑选数字 29, 6 和 10。
291 + 6(-3) + 10*(-1) = 1

示例 3:

输入:nums = [3,6]
输出:false

提示:

  • 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
  • 1<=nums[i]<=1091 <= nums[i] <= 10^91<=nums[i]<=109

分析:

解决本题需要学习下 裴蜀定理(Bézout’s identity)。

多个整数之间的裴蜀定理

a1....ana_1....a_na1....annnn 个整数,ddd 是这个nnn个数的最大公约数,那么就肯定存在 x1....xnx_1....x_nx1....xn 使得 a1∗x1...an∗xn=da_1 * x_1...a_n * x_n = da1x1...anxn=d

特殊的情况是,只要当 a1...ana_1...a_na1...an 中有存在两个或以上的数互质,那么就一定存在 x1,x2...xnx_1,x_2...x_nx1,x2...xn 使得 a1∗x1+a2∗x2...an∗xn=1a_1 * x_1 + a_2 * x_2...a_n * x_n = 1a1x1+a2x2...anxn=1

时间复杂度:O(nlogm)O(nlogm)O(nlogm)

代码:

class Solution {
public://求 a 和 b 的最大公约数int gcd(int a,int b){return b ? gcd(b,a%b) : a;}bool isGoodArray(vector<int>& nums) {int g = 0;for(auto x:nums){g = gcd(g,x);//g == 1 说明 nums 中一定存在两个数以上的互质if(g == 1) break;}return g == 1;}
};

相关文章:

Leetcode.1250 检查「好数组」

题目链接 Leetcode.1250 检查「好数组」 Rating &#xff1a; 1983 题目描述 给你一个正整数数组 nums&#xff0c;你需要从中任选一些子集&#xff0c;然后将子集中每一个数乘以一个 任意整数&#xff0c;并求出他们的和。 假如该和结果为 1&#xff0c;那么原数组就是一个「…...

WMS系统推荐,如何选到适合企业的仓库管理系统

市场上有很多WMS系统&#xff0c;但是现在很多仓库管理系统都在使用WMS系统。那么在选择WMS系统时应该考虑什么呢&#xff1f;明确业务发展特征&#xff0c;准确表达能力目标许多物流企业在选择物流管理系统时&#xff0c;往往会被物流管理系统的整体系统所迷惑&#xff0c;在功…...

C语言的期末复习

&#x1f308;博客主页&#xff1a;卿云阁 &#x1f48c;欢迎关注&#x1f389;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; &#x1f31f;本文由卿云阁原创&#xff01; &#x1f64f;作者水平很有限&#xff0c;如果发现错误&#xff0c;请留言轰炸哦&#xff01;万分感谢&a…...

强化学习之DQN论文介绍

强化学习之DQN论文介绍DQN摘要介绍问题特点经验回放相关工作实验算法流程结论DQN 摘要 1.基于Q-learning从高维输入学习到控制策略的卷积神经网络。 2.输入是像素&#xff0c;输出是奖励函数。 3.主要训练、学习Atari 2600游戏&#xff0c;在6款游戏中3款超越人类专家。 介绍 …...

使用luaBridge添加自己的C++脚本插件能力

概述 如果我们有一个应用需要频繁的更改业务逻辑,但是基础功能不变,那么我们可以将基础功能作为底层接口,上层的功能按照脚本方式来编写。很多插件都这样的原理,比如我们的浏览器的JS就这样,小程序也是这样的原理,我们使用C++也很容易实现这样的功能。 lua是最小最精致的…...

再拾起博客

一切要从去年12月27日被裁员的那天说起。 那天是星期二&#xff0c;和平常一样&#xff0c;8点20的闹钟响起&#xff0c;但我习惯性的磨蹭到8点40起床&#xff0c;洗漱完成后9点过几分出门&#xff0c;骑车20多分钟几乎是踩点到的公司&#xff0c;正当我坐在工位准备平复心情切…...

Mybatis流式游标查询-大数据DB查询OOM查询问题

问题场景Mysql数据处理类型分以下三种com.mysql.cj.protocol.a.result.ResultsetRowsStatic&#xff1a;普通查询&#xff0c;将结果集一次性全部拉取到内存com.mysql.cj.protocol.a.result.ResultsetRowsCursor&#xff1a;游标查询&#xff0c;将结果集分批拉取到内存&#x…...

以before为例 完成一个aop代理强化方法案例

观看本文 首先 您需要做好Spring aop的准备工作 具体可以参考我的文章 java Spring aop入门准备工作 首先 我们创建一个包 我这里叫 Aop 然后在Aop包下创建一个类 叫 User 参考代码如下 package Aop;public class User {public void add(){System.out.println("add....…...

好记性不如烂笔头之Java基础复习笔记

未完待续。。。 代码块先于构造方法执行&#xff0c;不管类中有多少个代码块&#xff0c;都会先将所有代码块执行完再执行构造方法和其他方法。类中如果没有自定义的构造方法&#xff0c;那么JVM会提供默认的无参构造方法&#xff1b;如果类中有自定义的构造方法&#xff0c;那…...

MyBatisPlus

这里写目录标题1.MyBatisPlus概述2.MyBatisPlus的开发步骤2.1 MyBatisPlus的CRUD操作2.2 MyBatisPlus的分页查询3.MyBatisPlus的DQL编程控制(封装sql)3.1 条件查询方式3.1.1 条件查询3.1.2 组合条件3.1.3 Null值处理3.2 查询投影-设置【查询字段、分组、分页】3.2.1 查询结果包…...

【C语言】编程初学者入门训练(11)

文章目录101. 矩阵相等判定102. 上三角矩阵判定103. 矩阵转置104. 矩阵交换105. 杨辉三角106. 井字棋107. 小乐乐与进制转换108. 小乐乐求和109. 小乐乐定闹钟110. 小乐乐排电梯101. 矩阵相等判定 问题描述&#xff1a;KiKi得到了两个n行m列的矩阵&#xff0c;他想知道两个矩阵…...

HTTP 1.1响应码

HTTP 1.1响应码 响应码和信息含义HttpURLConnection1XX信息100 Continue服务器准备接受请求主体&#xff0c;客户端应当发送请求主体&#xff1b;这允许客户端在请求中发送大量数据之前询问服务器是否将接受请求N/A101 Switching Protocols服务器接受客户端在Upgrade首部字段中…...

常用设计模式介绍

java设计模式类型创建型模式&#xff1a;将对象的创建与使用分离结构型模式&#xff1a;如何将类和对象按照某种布局组成更大的格局行为型模式&#xff1a;用于描述类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务23种设计模式介绍1.单例&#xff08;Singleton&…...

关于货物物品横竖摆放的问题

货车内宽是2.4米。考虑到最多装载&#xff0c;长宽130100的货品&#xff0c;应该横竖摆放。 横竖摆放的数量如何自动计算呢&#xff1f; 采用数学公式&#xff0c;计算如下&#xff1a; 横向摆放数(int)(横长竖高)*数量/4/横长 竖向摆放数数量-横向摆放数 结果如下&#x…...

人员定位需求多,场景目标各不同

GPS技术为现代人带来了许多便利&#xff0c;也提供了诸多基于位置的新型服务。随着科技的发展&#xff0c;人员位置信息在如今的生产生活中也越发重要起来。因此&#xff0c;不同行业领域开始关注人员定位&#xff0c;尤其关注室内人员定位。室内人员定位需求从目的性出发&…...

怎么解决首屏加载速度过慢的问题

怎么解决首屏加载速度过慢的问题首屏加载速度指的是什么&#xff1f;解决方法首屏加载速度指的是什么&#xff1f; 首屏加载速度指的是浏览器从响应用户输入网站地址到首屏内容渲染完成的时间。值得注意的是此时整个网页不一定要全部渲染完成&#xff0c;只需展示当前视窗所需要…...

3d视觉相关论文阅读目录汇总

目录3d视觉综述论文 Deep Learning for 3D Point Clouds: A Survey 基础概念 3d目标检测常见基础概念 3d目标检测 & 自动驾驶 数据集 3d目标检测数据集介绍&#xff08;数据格式&#xff0c;保存形式&#xff0c;适配算法库等&#xff09; KITTI数据集 Waymo数据集 nu…...

最简单的计算机视觉

百度为大家提供了计算机视觉模型。能够识别图像中的相关物体。 给大家介绍计算机视觉工具&#xff0c;EasyDL是能够识别物体&#xff0c;图像分类的工具&#xff0c;可以在线&#xff0c;也可以本地下载&#xff0c;本地下载大概1.5G。 图像识别真实距离。 图片真实距离/物体…...

泛微采知连,为组织提供安全、合规、智能的数字化文控系统

作为市场主体&#xff0c;企业需要建立健全的质量管理体系&#xff0c;并且及时更新&#xff0c;以应对激烈的市场竞争&#xff0c;实现企业可持续发展。 质量体系在很大程度上通过文件化的形式表现出来。《质量管理体系要求》(GB/T19001—2016/ISO9001&#xff1a;2015)标准指…...

Python if else对缩进的要求

前面的《Python if else》一节展示了选择结构的三种基本形式&#xff0c;并给出了实例演示&#xff0c;但是大家在编写代码过程中仍然要注意一些细节&#xff0c;尤其是代码块的缩进&#xff0c;这对 if else 选择结构极其重要。 Python 是以缩进来标记代码块的&#xff0c;代…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...