每日算法系列【LeetCode 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^5
  • 1 <= nums[i] <= 10^9

题解

这题名义上是困难难度,实际上只要知道一些数学知识,就非常的简单。

首先题目中要求挑选出一些数,然后给每个数分配整数系数,加权求和等于 1 。
仔细想一想就不对劲,全选不是一样嘛?有些数系数分配 0 就行了。

假设系数分别是 $x_1, x_2, \ldots, x_n$ ,那么问题就变成了求解下面的多元一次方程有整数解的条件:
$$
a_1 x_1 + a_2 x_2 + \dots + a_n x_n = 1
$$
如果你数学基础不错的话,一眼就会发现条件就是所有非零数的最大公约数为 1
$$
gcd(a_1, a_2, \ldots, a_n) = 1, a_i \neq 0
$$

证明参见 n 个数的裴蜀定理

代码

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int x = nums[0], n = nums.size();
        for (int i = 1; i < n; ++i) {
            if (nums[i]) x = gcd(x, nums[i]);
        }
        return x == 1;
    }

    int gcd(int x, int y) {
        return x%y ? gcd(y, x%y) : y;
    }
};

后记

最后不管是用时还是空间消耗都超越了100%的用户。


   转载规则


《每日算法系列【LeetCode 1250】检查「好数组」》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
每日算法系列【LeetCode 992】K个不同整数的子数组 每日算法系列【LeetCode 992】K个不同整数的子数组
题目描述给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。) 返回 A 中好子数组的数目
2020-01-11
下一篇 
每日算法系列【LeetCode 1004】最大连续1的个数 III 每日算法系列【LeetCode 1004】最大连续1的个数 III
题目描述给定一个由若干 0 和 1 组成的数组 A ,我们最多可以将 K 个值从 0 变成 1 。 返回仅包含 1 的最长(连续)子数组的长度。 示例1 输入: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出:
2020-01-09
  目录