Daily LeetCode – day0169 1819. Number of Different Subsequences GCDs

// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    if (GCDs[num / i] == 0) {
                        GCDs[num / i] = num;
                    } else {
                        GCDs[num / i] = gcd(GCDs[num / i], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
学习笔记:
强迫自己进步的一天,这是一道困难题。
思路用得很巧妙,本来是先归类再计算,然后转化成了一边分类分类进去就顺便计算。
题目说题目数字在20万以内,那么最大的最大公约数也就是20万了。

然后我们可以逐一去考虑,每一个最大公约数怎么检验是否符合呢?
比如要校验4,那么得把所有4的正整数倍数找出来:
情况1:4,8,12,16,20这样的,那么有4在,肯定最大公约数肯定是4了。
情况2:8,16,64这样的,那么最大公约数其实是8,那么就不存在最大公约数为4的情况。
情况3:8,12,16,20这样的,没有4在,但是他们的最大公约数也是4。
总结就是把倍数找出来,然后连续求最大公约数。

接着就遇到了死胡同,这样一个个校验,从1到200000,挑出来要遍历一整遍,然后连续求最大公约数也要时间。总共加起来要做200000个一整遍。

巧妙的来了,其实只要遍历一整遍,每次找到是某个数的倍数,那么就分类顺便把连续求最大公约数的步骤也做了。这样只需要弄个200001的空间存当前的最大公约数们就可以啦。

最后统计有多少个数字的最大公约数是自己那也就是存在。
// 1819. Number of Different Subsequences GCDs
class Solution {
    public int countDifferentSubsequenceGCDs(int[] nums) {
        int[] GCDs = new int[200001];
        for (int num : nums) {
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    if (GCDs[i] == 0) {
                        GCDs[i] = num;
                    } else if (GCDs[i] != i) {
                        GCDs[i] = gcd(GCDs[i], num);
                    }
                    int numOverI = num / i;
                    if (GCDs[numOverI] == 0) {
                        GCDs[numOverI] = num;
                    } else if (GCDs[numOverI] != numOverI) {
                        GCDs[numOverI] = gcd(GCDs[numOverI], num);
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < 200001; ++i) {
            if (GCDs[i] == i) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
接下来又优化了代码,从572ms变到了446ms。
就是说一旦中途发现gcds[i]已经等于i了,那就没有下探空间了。
所以不需要再调用gcd函数递归去求了。
gcd[num / i]已经等于num / i也是一样的道理。
用上变量可以更快,不用反复去除以。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注