class Solution {
public:
bool isGoodArray(vector<int>& nums) {
}
};
1250. 检查「好数组」
给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
示例 1：
输入：nums = [12,5,7,23] 输出：true 解释：挑选数字 5 和 7。 5*3 + 7*(-2) = 1
示例 2：
输入：nums = [29,6,10] 输出：true 解释：挑选数字 29, 6 和 10。 29*1 + 6*(-3) + 10*(-1) = 1
示例 3：
输入：nums = [3,6] 输出：false
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^9原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 22.2 MB, 提交时间: 2023-02-15 09:27:39
class Solution:
def isGoodArray(self, nums: List[int]) -> bool:
return math.gcd(*nums) == 1
java 解法, 执行用时: 3 ms, 内存消耗: 50 MB, 提交时间: 2023-02-15 09:27:14
class Solution {
public boolean isGoodArray(int[] nums) {
int divisor = nums[0];
for (int num : nums) {
divisor = gcd(divisor, num);
if (divisor == 1) {
break;
}
}
return divisor == 1;
}
public int gcd(int num1, int num2) {
while (num2 != 0) {
int temp = num1;
num1 = num2;
num2 = temp % num2;
}
return num1;
}
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 47 MB, 提交时间: 2023-02-15 09:26:34
/**
* @param {number[]} nums
* @return {boolean}
*/
var isGoodArray = function(nums) {
let divisor = nums[0];
for (const num of nums) {
divisor = gcd(divisor, num);
if (divisor === 1) {
break;
}
}
return divisor === 1;
}
const gcd = (num1, num2) => {
while (num2 !== 0) {
const temp = num1;
num1 = num2;
num2 = temp % num2;
}
return num1;
};
golang 解法, 执行用时: 32 ms, 内存消耗: 9.2 MB, 提交时间: 2023-02-15 09:26:09
func isGoodArray(nums []int) bool {
g := 0
for _, x := range nums {
g = gcd(g, x)
if g == 1 {
return true
}
}
return false
}
func gcd(a, b int) int { for a != 0 { a, b = b%a, a }; return b }
python3 解法, 执行用时: 40 ms, 内存消耗: 22.4 MB, 提交时间: 2023-02-15 09:24:49
'''
裴蜀定理
若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y, ax+by都一定是d的倍数，
特别地，一定存在整数x,y，使ax+by=d成立。
'''
class Solution:
def isGoodArray(self, nums: List[int]) -> bool:
return functools.reduce(math.gcd, nums) == 1