跳到主要内容

1250.检查「好数组」

链接：1250.检查「好数组」
难度：Hard
标签：数组、数学、数论
简介：给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个任意整数，并求出他们的和。假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

题解 1 - cpp

编辑时间：2023-02-15
执行用时：44ms
内存消耗：28.5MB
编程语言：cpp
解法介绍：裴蜀定理。

class Solution {
public:
    int gcd(int a, int b) {
        if (!b) return a;
        if (a < b) return gcd(b, a);
        return gcd(b, a % b);
    }
    bool isGoodArray(vector<int>& nums) {
        int res = nums[0];
        for (auto &num : nums) {
            res = gcd(res, num);
            if (res == 1) break;
        }
        return res == 1;
    }
};

题解 2 - python

编辑时间：2023-02-15
执行用时：92ms
内存消耗：22.7MB
编程语言：python
解法介绍：同上。

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        def gcd(a, b):
            if not b:
                return a
            if a < b:
                return gcd(b, a)
            return gcd(b, a % b)
        res = nums[0]
        for num in nums:
            res = gcd(res, num)
            if res == 1:
                break
        return res == 1

题解 3 - rust

编辑时间：2023-02-15
执行用时：4ms
内存消耗：3.4MB
编程语言：rust
解法介绍：同上。

fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 {
        a
    } else if a < b {
        gcd(b, a)
    } else {
        gcd(b, a % b)
    }
}
impl Solution {
    pub fn is_good_array(nums: Vec<i32>) -> bool {
        let mut res = nums[0];
        for num in nums {
            res = gcd(res, num);
            if res == 1 {
                break;
            }
        }
        res == 1
    }
}

题解 1 - cpp
题解 2 - python
题解 3 - rust