2748.力扣每日一题6/20 Java

题目：
给你一个下标从 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 的 最大公因数 。

示例 1：

输入：nums = [2,5,1,4]
输出：5
解释：nums 中共有 5 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 2 ，nums[1] 的最后一个数字是 5 。2 和 5 互质，因此 gcd(2,5) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 2 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。2 和 5 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。2 和 5 互质，因此 gcd(1,4) == 1 。
因此，返回 5 。
示例 2：

输入：nums = [11,21,12]
输出：2
解释：共有 2 组美丽下标对：
i = 0 和 j = 1 ：nums[0] 的第一个数字是 1 ，nums[1] 的最后一个数字是 1 。gcd(1,1) == 1 。
i = 0 和 j = 2 ：nums[0] 的第一个数字是 1 ，nums[2] 的最后一个数字是 2 。gcd(1,2) == 1 。
因此，返回 2 。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 9999
• nums[i] % 10 != 0

解题思路

首先，我们需要明确题目要求的是找出数组中所有“美丽数对”的数量。一个“美丽数对”是指数组中的两个数 (x, y)，其中 x 的最高位数字与 y 的个位数字互质（即最大公约数为1）。

为了高效地解决这个问题，我们可以使用一个数组 cnt 来记录每个数字作为最高位数字的出现次数。然后，对于数组 nums 中的每一个数 num，我们分别提取其最高位数字 firstDigit 和个位数字 lastDigit。

1. 提取个位数字：通过取余操作 num % 10 可以得到 num 的个位数字。
2. 提取最高位数字：我们需要通过循环不断地将 num 除以10，直到 num 的值小于10，此时 num 就是原来的最高位数字。
3. 检查互质关系：对于 lastDigit，我们遍历 cnt 数组，检查每个作为最高位数字的数字 i 是否与 lastDigit 互质（即 gcd(i, lastDigit) == 1）。如果互质且 cnt[i] > 0（即 i 作为最高位数字在数组中出现过），则我们将 cnt[i] 加到结果 ans 中，因为对于每一个这样的 i，都有 cnt[i] 个数与当前的 num 形成“美丽数对”。
4. 更新计数数组：在遍历完 num 的所有相关操作后，我们将 firstDigit 的出现次数在 cnt 数组中加1。

代码实现：

class Solution {  
    public int countBeautifulPairs(int[] nums) {  
        int ans = 0;  
        int[] cnt = new int[10]; // 用于记录每个数字作为最高位数字的出现次数  
        for (int num : nums) {  
            int lastDigit = num % 10; // 提取个位数字  
            int temp = num;  
            while (temp >= 10) { // 提取最高位数字  
                temp /= 10;  
            }  
            int firstDigit = temp;  
  
            // 检查与个位数字互质的最高位数字的出现次数  
            for (int i = 1; i < 10; i++) {  
                if (cnt[i] > 0 && gcd(i, lastDigit) == 1) {  
                    ans += cnt[i];  
                }  
            }  
  
            // 更新最高位数字的出现次数  
            cnt[firstDigit]++;  
        }  
        return ans;  
    }  
  
    private int gcd(int a, int b) {  
        return b == 0 ? a : gcd(b, a % b);  
    }  
}

第二种解法

解题思路：

1. 初始化：
   • res 用于存储美丽对的总数，初始化为0。
   • cnt 是一个长度为10的数组，用于记录0到9这10个数字作为最高位数字在数组中出现的次数。注意，由于数字的最高位不可能是0（除非数字本身为0，但这种情况在这里被忽略了），所以实际上cnt[0]不会被使用。
2. 遍历数组中的每个数字：
   • 使用增强型for循环遍历输入数组nums中的每个数字x。
3. 检查个位数与每个可能的最高位数字是否互质：
   • 使用内层循环遍历1到9的每个数字y。
   • 计算x的个位数（x % 10）与y的最大公约数。
   • 如果最大公约数为1（即它们互质），则意味着x的个位数与某个数字的最高位y可以形成一个美丽对。因此，将cnt[y]（即最高位为y的数字的个数）加到res
   • 提取最高位数字并更新计数：
     • 我们可以使用另一个while循环来提取x的最高位数字。
     • 当提取到最高位数字后，增加cnt数组中对应位置的计数。
   • 返回结果：
     • 返回计算得到的美丽对的总数res。

哈希表

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int res = 0;
        int[] cnt = new int[10];
        for (int x : nums) {
            for (int y = 1; y <= 9; y++) {
                if (gcd(x % 10, y) == 1) {
                    res += cnt[y];
                }
            }
            while (x >= 10) {
                x /= 10;
            }
            cnt[x]++;
        }
        return res;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}