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

2748.美丽下标对的数目【简单】

题目：

给你一个下标从 0 开始的整数数组 nums 。如果下标对 i、j 满足 0 ≤ i

返回 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 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. 对代码的优化和改进，例如减少重复计算和提高代码的可读性。

  ---

  

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