Day 28：2748. 美丽下标对的数目

Leetcode 2748. 美丽下标对的数目

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i < j < nums.length ，如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 ，则认为 nums[i] 和 nums[j] 是一组 美丽下标对 。
返回 nums 中 美丽下标对 的总数目。
对于两个整数 x 和 y ，如果不存在大于 1 的整数可以整除它们，则认为 x 和 y 互质 。换而言之，如果 gcd(x, y) == 1 ，则认为 x 和 y 互质，其中 gcd(x, y) 是 x 和 y 的 最大公因数 。

判断两个数字是否互质，并不麻烦，从它们最小的值开始遍历到 2，看是否都能整除。当然，这肯定不是最优的算法。但在此题中，数字范围在 10 以内，因此计算也不是特别大。
再者，用两个数组分别保存数组值的第一个数字和最后一个数字，在判断互质时就不用每次都去计算第一个数字和最后一个数字了。

完整代码

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[] first = new int[n]; // 第一个数字
        int[] last = new int[n]; // 最后一个数字
        for (int i = 0; i < n; i++) {
            last[i] = nums[i] % 10;
            first[i] = getFirst(nums[i]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(first[i], last[j]) ==  1) res++;
            }
        }
        return res;
    }

    public int getFirst(int num) {
        while (num >= 10) num /= 10;
        return num;
    }

    public int gcd(int a, int b) {
        for (int i = Math.min(a, b); i > 1; i--) {
            if ((a % i == 0) && (b % i == 0)) return i;
        }
        return 1;
    }
}