数据结构与算法实例详解--数学、数组 相结合

当数学与数组相结合时，可以产生许多有趣的结果和应用。比如：

1. 线性代数：数组（尤其是矩阵）在多维数据处理中至关重要。线性代数提供了矩阵运算的方法，可以用来解决方程组、进行变换等。

2. 数据分析与统计：数组用于存储数据，结合数学统计方法，可以用来进行数据分析、模型拟合、回归分析等。

3. 算法设计：许多算法（如搜索算法、排序算法、动态规划等）依赖于数组来存储和处理数据。数学为这些算法提供了理论依据和优化的方法。

4. 图形和图像处理：数组可以表示图像中的像素，通过数学运算（如傅里叶变换、卷积等）来处理和分析图像数据。

5. 机器学习：在机器学习中，数组（常用的多维数组称为张量）是存储训练数据和模型参数的基本结构，数学的优化方法（如梯度下降）用于训练模型。

6. 优化问题：许多实际问题可以通过将其表示为数组并应用数学优化技术来解决，例如线性规划、整数规划等。

7. 数论与加密：在数论中，数组可以用来表示各种数的集合，结合数学理论可以用于密码学的构建，例如公钥加密算法。

由此可见，数学和数组的结合在科学、工程、经济学、计算机科学等各个领域都发挥着重要作用，产生了无数创新和实际应用。

那我们今天的实例题目会产生什么样的影响呢，直接上题：

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

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

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

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

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

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

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