餐厅网站建设方案,爱站工具想说超人下拉系统,单本小说wordpress,区域工业互联网平台每日一题题目描述解题核心解法一#xff1a;数论题目描述
题目链接#xff1a;1250. 检查「好数组」
给你一个正整数数组 nums#xff0c;你需要从中任选一些子集#xff0c;然后将子集中每一个数乘以一个 任意整数#xff0c;并求出他们的和。 假如该和结果为 1#x…
每日一题题目描述解题核心解法一数论题目描述
题目链接1250. 检查「好数组」
给你一个正整数数组 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 10^51 nums[i] 10^9 解题核心
判断是否为好数组的关键就是判断∑i1nai×xi1\sum_{i1}^{n} a_{i} \times x_{i} 1∑i1nai×xi1是否有解根据题目提示可以参考裴蜀定理
解法一数论
题目等价于求数组中的全部数字的最大公约数是否等于1若等于1则原数组为「好数组」否则不是。
public boolean isGoodArray(int[] nums) {int res 0;for (int num : nums) {res gcd(res, num);if (res 1) return true;}return false;
}
//辗转相除法
public int gcd(int a, int b) {return b 0 ? a : gcd(b, a % b);//b等于0说明上一次递归调用的时候b是a的整数倍
}
