分销平台是什么意思,网站如何从行为数据进行优化,手机网站布局教程,查找人网站 优帮云题目
题目链接
LeetCode2748.美丽下标对的数目
题目描述
给你一个下标从 0 开始的整数数组 nums 。
如果下标对 i、j 满足 0 ≤ i j nums.length #xff0c;
如果 nums[i] 的 第一个数字 和 nums[j] 的 最后一个数字 互质 #xff0c;
则认为 nums[i] 和 nums…题目
题目链接
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,满足0ijnums.length。如果nums[i]的第一个数和nums[j]的最后一个数字互质则这是一对美丽下标对。关键在于取得是nums[i]的第一个数字以及nums[j]的最后一个数字。
Q如何判断两个数字是否互质概念和算法 A1互质两个数没有比1大的公约数就是互质。 A2gcd辗转相除法。这里用文字描述一下先毕竟能用大白话说出来写成代码也不难。传进来两个数a和b把b变成a%ba变成原来的b然后判断b是不是0。如果b是0则返回a的值。a就是最大公约数。But怎么用gcd判断俩数是否互质呢如果两个数互质那么gcd的返回结果就是1调用完gcd检查一下就行了。
Q我已经知道了美丽下标对的定义和判断两个数是否互质的方法那么接下来如何编写Solution。 A理解清输入、输出的要求再想中间的运算逻辑。
输入一个整型数组。一定有两个或两个以上的元素 输出返回这个数组中美丽下标对的数目。运算这不就是让咱遍历数组吗因为题目已经要求只有当ij的时候才算数了。所以只需要从前往后遍历多遍数组然后每个对子都判断一次就好了。
Java版Solution
class Solution {public int countBeautifulPairs(int[] nums) {int res0;int[] dp new int[10];for(int x:nums){for(int j1;j10;j){if(gcd(x%10,j)1){resdp[j];}}while(x10)x/10;dp[x];}return res;}private int gcd(int a,int b){return b0?a:gcd(b,a%b);}
}总结
出问题的地方
下标没理清楚 内层循环每次都应该遍历到最后应该是nums.length起始位置应该是i1外层循环只需要遍历到nums.length-1。 题目定义没理清楚 题目都给了第二个例子了我没看见真的是。
优化思路
抄袭的官方题解
只用遍历一次nums数组对于第一个数只需要保存下来它的第一个数字存在咱定义的哈希表里。哈希表在这个题里下标和元素分别表示下标开头的数字有元素个。在之后遍历的时候都是先取这个数的最后一个数字然后拿它和0到9进行gcd如果结果为1就让结果加加加多少加上哈希表里这个数字对应的元素的值。然后取这个数字的第一个数字同样保存在哈希表中。只需要让对应下标的元素加加就行了
