urfread刷算法题day1|LeetCode2748.美丽下标的数目

题目

题目链接

LeetCode2748.美丽下标对的数目

题目描述

给你一个下标从 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 和 1 互质，因此 gcd(2,1) == 1 。
i = 1 和 j = 2 ：nums[1] 的第一个数字是 5 ，nums[2] 的最后一个数字是 1 。5 和 1 互质，因此 gcd(5,1) == 1 。
i = 1 和 j = 3 ：nums[1] 的第一个数字是 5 ，nums[3] 的最后一个数字是 4 。5 和 4 互质，因此 gcd(5,4) == 1 。
i = 2 和 j = 3 ：nums[2] 的第一个数字是 1 ，nums[3] 的最后一个数字是 4 。1 和 4 互质，因此 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

题目解析

Q：什么是美丽下标对？（看完题目描述之后，背出来）
A：假如有一个数组nums，其中有两个下标i、j,满足0<=i<j<nums.length。如果nums[i]的第一个数和nums[j]的最后一个数字互质，则这是一对美丽下标对。关键在于，取得是nums[i]的第一个数字，以及nums[j]的最后一个数字。

Q：如何判断两个数字是否互质？（概念和算法）
A1：互质：两个数没有比1大的公约数，就是互质。
A2：gcd：辗转相除法。这里用文字描述一下先，毕竟能用大白话说出来，写成代码也不难。传进来两个数a和b，把b变成a%b，a变成原来的b，然后判断b是不是0。如果b是0，则返回a的值。a就是最大公约数。But！怎么用gcd判断俩数是否互质呢？如果两个数互质，那么gcd的返回结果就是1，调用完gcd检查一下就行了。

Q：我已经知道了美丽下标对的定义和判断两个数是否互质的方法，那么接下来如何编写Solution。
A：理解清输入、输出的要求，再想中间的运算逻辑。

1. 输入：一个整型数组。一定有两个或两个以上的元素
   
2. 输出：返回这个数组中美丽下标对的数目。
3. 运算：这不就是让咱遍历数组吗？因为题目已经要求只有当i<j的时候，才算数了。所以只需要从前往后遍历多遍数组，然后每个对子都判断一次就好了。

Java版Solution

class Solution {public int countBeautifulPairs(int[] nums) {int res=0;int[] dp = new int[10];for(int x:nums){for(int j=1;j<10;j++){if(gcd(x%10,j)==1){res+=dp[j];}}while(x>=10)x/=10;dp[x]++;}return res;}private int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
}

总结

出问题的地方

• 下标没理清楚
  • 内层循环每次都应该遍历到最后，应该是<nums.length，起始位置应该是i+1
  • 外层循环只需要遍历到nums.length-1。
• 题目定义没理清楚
  • 题目都给了第二个例子了，我没看见，真的是。

优化思路

抄袭的官方题解

1. 只用遍历一次nums数组
2. 对于第一个数，只需要保存下来它的第一个数字，存在咱定义的哈希表里。哈希表在这个题里，下标和元素分别表示，（下标）开头的数字有（元素）个。
3. 在之后遍历的时候，都是先取这个数的最后一个数字，然后拿它和0到9进行gcd，如果结果为1，就让结果加加，加多少？加上哈希表里这个数字对应的元素的值。
4. 然后取这个数字的第一个数字，同样保存在哈希表中。（只需要让对应下标的元素加加就行了）