力扣每日一题 6/20 数学+数组

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 的 最大公因数 。

示例 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

分析问题：

       读完题，第一思路就是模拟题目，跟着题目的要求遍历nums列表，然后符合题意则计数。但这里需要注意的是，j>i 并且只取nums[i]的第一位数字以及nums[j]的最后一位数字，什么意思呢？

       也就是说这里我们要进行一个字符串切割，并且后续我们比对的时候也只需要比对10以下的数字是否互质即可，那么这里我们就可以用简单的方法，没有必要全部去比对，只需要知道nums[i]的第一位数字和nums[j]的最后一位数字是什么我们就能直接得到是否互质这个答案，可以大大减小我们的时间复杂度。接下来请看代码实现以及两者之间的复杂度比对。

代码实现：

优化前：

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        import math
        def pan(m,n):
            if math.gcd(m,n)==1: return True
            return False
        v=0
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if pan(int(str(nums[i])[0]),int(str(nums[j])[-1])): v+=1
        return v

优化后：

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        factor = {
            1: [1, 2, 3, 4, 5, 6, 7, 8, 9],
            2: [1, 3, 5, 7, 9],
            3: [1, 2, 4, 5, 7, 8],
            4: [1, 3, 5, 7, 9],
            5: [1, 2, 3, 4, 6, 7, 8, 9],
            6: [1, 5, 7],
            7: [1, 2, 3, 4, 5, 6, 8, 9],
            8: [1, 3, 5, 7, 9],
            9: [1, 2, 4, 5, 7, 8]
        }
        last = [0] * 10
        for num in nums:
            last[num % 10] += 1
 
        count = 0
        for i, num in enumerate(nums):
            last[num % 10] -= 1
            while num // 10 > 0:
                num //= 10
            for gcd_num in factor[num]:
                count += last[gcd_num]
        return count

通过对比两者的提交耗时，可以直观的发现优化后的复杂度有大大降低。

总结：

优化后代码详解：

1. factor 字典：定义了每个数字的因数列表。例如，数字 1 的因数是 1、2、3、4、5、6、7、8、9，数字 2 的因数是 1、3、5、7、9，以此类推。
2. last 列表：用于记录每个数字在列表中出现的次数。初始时，每个数字的出现次数都为 0。
3. 遍历列表 nums：对于每个数字 num，将其在 last 列表中的出现次数加 1。
4. 再次遍历列表 nums：对于每个数字 num，将其在 last 列表中的出现次数减 1。然后，通过不断除以 10，将数字 num 的首位数字提取出来。
5. 对于提取出来的首位数字，遍历其因数列表 factor[num]。对于每个因数 gcd_num，将其在 last 列表中的出现次数加到 count 变量中。
6. 最后，返回 count 变量，即美丽数对的数量。

主要考察了以下几个方面：

1. 对字典和列表的使用：通过 factor 字典存储数字的因数列表，通过 last 列表记录数字的出现次数。
2. 循环和条件判断：使用两个嵌套的循环遍历列表 nums，并根据条件进行计算。
3. 数学运算：涉及到除法和取余运算，用于提取数字的首位数字。
4. 问题解决能力：通过分析问题，设计合适的数据结构和算法来解决美丽数对的计算问题。

刷过这道题可以学到以下几点：

1. 如何使用字典和列表来存储和操作数据。
2. 如何使用循环和条件判断来解决问题。
3. 如何进行数学运算和处理数字。
4. 如何分析问题并设计有效的算法。
5. 对代码的优化和改进，例如减少重复计算和提高代码的可读性。

“别人总是以为你什么都有，但你只剩自己了。”——意难藏——