LeetCode每日一题4.13

1922. 统计好数字的数目

问题

问题分析

题目要求我们找到长度为 n 且满足特定条件（偶数下标处为偶数，奇数下标处为质数）的数字字符串的总数，并对 (10^9 + 7) 取余。

思路

1.枚举
生成所有可能的数字字符串：对于长度为 n 的数字字符串，总共有 (10^n) 种可能性。
检查每个字符串是否为好数字：
偶数下标处的数字必须是偶数（0, 2, 4, 6, 8）。
奇数下标处的数字必须是质数（2, 3, 5, 7）。
计数满足条件的字符串数量。
2. 数学分析
定义好数字的条件：
偶数下标处的数字必须是偶数（0, 2, 4, 6, 8）。
奇数下标处的数字必须是质数（2, 3, 5, 7）。
计算每个位置的可选数字数量：
偶数下标处有 5 种选择（0, 2, 4, 6, 8）。
奇数下标处有 4 种选择（2, 3, 5, 7）。
根据 n 的长度计算总数：
如果 n 为 1，则只有偶数下标，因此结果为 5。
如果 n 大于 1，可以通过数学方法快速计算结果。

代码

1. 枚举

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10 ** 9 + 7

        def is_good_number(num_str):
            for i, digit in enumerate(num_str):
                if i % 2 == 0:  # 偶数下标
                    if digit not in '02468':
                        return False
                else:  # 奇数下标
                    if digit not in '2357':
                        return False
            return True

        count = 0
        for i in range(10 ** n):
            num_str = str(i).zfill(n)  # 确保长度为 n，前导零
            if is_good_number(num_str):
                count += 1

        return count % MOD

2. 数学方法

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        # 偶数位的数量
        even_positions = (n + 1) // 2
        # 奇数位的数量
        odd_positions = n // 2

        # 计算结果
        result = (pow(5, even_positions, MOD) * pow(4, odd_positions, MOD)) % MOD
        return result

复杂度分析

1. 枚举：
   时间复杂度：对于长度为 n 的数字字符串，需要检查 (10^n) 个字符串。当 n 较大时（例如 n >= 10），这种方法将变得极其缓慢。
   空间复杂度：生成和存储大量字符串也会消耗大量内存。
2. 数学分析；
   时间复杂度：(O(\log n))
   空间复杂度：(O(1))

学习

当字符串很大时，暴力枚举导致超时。

pow 函数被用来计算大数的幂并取模。

pow 函数在 Python 中有三种用法：

• pow(x, y)：计算 (x) 的 (y) 次幂，即 (x^y)。
• pow(x, y, z)：计算 (x^y \mod z)，即 (x) 的 (y) 次幂然后对 (z) 取模。

pow 在本问题中的应用
在本问题中，pow 函数的第三种用法被使用，具体为 pow(5, even_positions, MOD) 和 pow(4, odd_positions, MOD)。
pow(5, even_positions, MOD)：
(x = 5)（基数）
(y = even_positions)（指数）
(z = MOD)（模数，这里为 (10^9 + 7))
计算 (5^{even_positions} \mod (10^9 + 7))
pow(4, odd_positions, MOD)：
(x = 4)（基数）
(y = odd_positions)（指数）
(z = MOD)（模数，这里为 (10^9 + 7))
计算 (4^{odd_positions} \mod (10^9 + 7))

pow 函数的优势

高效性：
pow 函数采用快速幂算法（也称为平方乘算法），其时间复杂度为 (O(\log y))，相比于直接计算 (x^y)（时间复杂度为 (O(y))）要高效得多。
快速幂算法通过将指数 (y) 不断减半来减少计算量，例如 (x^8 = ((x²⁾2)^2)。
防止溢出：
在计算大数的幂时，结果可能会非常大，导致溢出。
pow(x, y, z) 在每次中间结果时都会取模，有效地防止了溢出问题

学习参考

：灵茶山艾府