---

0479. 最大回文数乘积

• 标签：数学、枚举
• 难度：困难

题目链接

• 0479. 最大回文数乘积 - 力扣

题目大意

描述：

给定一个整数 $n$。

要求：

返回可表示为两个 $n$ 位整数乘积的「最大回文整数」。因为答案可能非常大，所以返回它对 $1337$ 取余。

说明：

• $1 \le n \le 8$。

示例：

• 示例 1：

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987

• 示例 2：

输入：n = 1
输出：9

解题思路

思路 1：数学 + 枚举

这道题的核心思想是构造回文数并检查是否能分解为两个 $n$ 位整数的乘积。

具体思路如下：

1. 确定范围：

   • 两个 $n$ 位整数的最小值为 $10^{n-1}$，最大值为 $10^n - 1$。
   • 最大乘积为 $(10^n - 1)^2$。

2. 构造回文数：

   • 从大到小枚举所有可能的回文数（因为要找最大的）。
   • 对于 $2n$ 位的回文数，可以表示为：$p = \text{left} \times 10^n + \text{reverse(left)}$，其中 $\text{left}$ 为 $n$ 位数字。
   • 例如：$n = 2$ 时，$99$ 对应回文数 $9999$，$98$ 对应回文数 $9889$。

3. 检查回文数是否能分解：

   • 对于每个回文数 $p$，检查是否存在两个 $n$ 位整数 $a$ 和 $b$，使得 $a \times b = p$。
   • 由于 $p = a \times b$，则 $a$ 和 $b$ 中至少有一个不小于 $\sqrt{p}$。
   • 因此可以从 $a = \lfloor \sqrt{p} \rfloor$ 开始枚举到 $10^n - 1$（取较小值的上界）。

4. 返回结果：

   • 找到第一个可以分解的回文数 $p$，返回 $p \% 1337$。

关键点：

• 注意 $n = 1$ 的特殊情况，直接返回 $9$。
• 构造回文数时，需要处理奇数和偶数位数的情况。
• 通过反向构造回文数可以避免生成和检查所有数字。

思路 1：代码

class Solution:
    def largestPalindrome(self, n: int) -> int:
        # n = 1 的特殊情况
        if n == 1:
            return 9
        
        # 计算上下界
        upper = 10 ** n - 1  # n 位数的最大值
        lower = 10 ** (n - 1)  # n 位数的最小值
        
        # 从大到小枚举所有可能的回文数
        # 通过 left 构造回文数：left + reverse(left)
        for left in range(upper, lower - 1, -1):
            # 构造回文数 p
            p = int(str(left) + str(left)[::-1])
            
            # 检查是否能分解为两个 n 位数的乘积
            # 从 sqrt(p) 开始向下枚举，避免重复计算
            for divisor in range(upper, int(p ** 0.5) - 1, -1):
                if p % divisor == 0:
                    # 检查另一个因子是否在 [lower, upper] 范围内
                    if lower <= p // divisor <= upper:
                        return p % 1337
        
        # 理论上不会执行到这里
        return 0

思路 1：复杂度分析

• 时间复杂度：$O(10^{2n})$。外层循环枚举所有 $n$ 位数（共 $10^n - 10^{n-1}$ 个），内层循环在最坏情况下需要检查 $O(10^n)$ 个因子，但实际上由于从 $\sqrt{p}$ 开始枚举，实际时间复杂度会更低。
• 空间复杂度：$O(1)$。只使用了常数级别的额外空间。