X

LEETCODE 1250. Check If It Is a Good Array 解题思路分析

题目大意:

检查「好数组」

给你一个正整数数组 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1250

解题思路分析:

这道题开始没有想到解题思路,看了答案之后才恍然大悟。简单来说,核心思想是找到一组数字,如果他们的最大公约数为1,那么代表结果为true,反之为false。简单来做下证明:

证明:gcd方法代表求一组数的最大公约数,如果 gcd(x1, x2, x3,…)=t>1,则 a⋅x1+b⋅x2+c⋅x3+…必定是t的倍数,所以不可能找到一组系数使其和等于1。

对于数学类的问题,必须从数学角度去思考,除此之外并没有太好的解题方法。对于本题,能够在编程上学习到的点是如何求2个数的最大公约数,简单粗暴的方式是从较小数字到1之间逐个循环,看看当前数字是否能2个数整除,找到一个最大的即使最大公约数。不过这种方式显然效率不高,我们可以通过余数法来求解。对于两个整数x和y,我们先保证x大于等于y,接下来计算出x % y的(余数)值,再与y作为参数递归本方法,直到较小的数字y等于0时,x即为两数的最大公约数。

int gcd(int x, int y) { // 求最大公约数
    if(x < y) return gcd(y, x); // 保证x大于等于y
    if(y == 0) return x; // 当y为0时,x即为两数的最大公约数
    return gcd(y, x % y); // 否则继续递归
}

这是比较典型的算法,应该牢记下来,Leetcode之前的很多题目都用到过这一方法。

那么接下来,本题该如何求解?毕竟题目给出的子序列长度不一定为2,也就是说我们需要找到多个数的最大公约数。这其实也不难,我们可以从数组第一位开始向后循环,先计算出前两数字的最大公约数,然后在利用这个最大公约数与第3个数求最大公约数,直到所有数字循环结束,期间只要出现结果为1 的最大公约数,可直接返回true,如果直到循环结束仍未找到,返回false。

这里可能会有一个疑问,只从头到尾循环一次数组,能排查出所有的组合情况吗?答案是肯定的,举个例子,比如数组:

[2,4,7]

很明显看出2和4的最大公约数为2,4和7则为1,我们遍历一次数组并没有遍历过4和7这两个数的区间[1,2],但是我们利用了2和4的最大公约数去和7求解,实际上是遍历了,2和7以及4和7两种情况。

看下实现代码:

public boolean isGoodArray(int[] nums) {
    int x = nums[0];
    for(int y : nums){
        x = gcd(x, y); // 两两计算最大公约数
        // 最大公约数为1,返回true
        if(x==1) return true;
    }
    return false;
}

int gcd(int x, int y) { // 求最大公约数
    if(x < y) return gcd(y, x); // 保证x大于等于y
    if(y == 0) return x; // 当y为0时,x即为两数的最大公约数
    return gcd(y, x % y); // 否则继续递归
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 78.34% of Java online submissions for Check If It Is a Good Array.

Memory Usage: 51.1 MB, less than 100.00% of Java online submissions for Check If It Is a Good Array.Next challenges:

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1250-check-if-it-is-a-good-array-解题思路分析/
Categories: leetcode
kwantong: