标签: 数学
难度: Hard
给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。
示例 1:
输入：n = 2 输出：987 解释：99 x 91 = 9009, 9009 % 1337 = 987
示例 2:
输入： n = 1 输出： 9
提示:
1 <= n <= 8
Submission
运行时间: 27 ms
内存: 15.9 MB
class Solution:
def largestPalindrome(self, n: int) -> int:
# 1 9 9
# 2 9009 987
# 3 906609 123
# 4 99000099 597
# 5 9966006699 677
# 6 999000000999 1218
# 7 99956644665999 877
# 8 9999000000009999 475
for part in range(10**n-1, 10**(n-1)-1, -1):
cur = int(str(part)+str(part)[::-1])
if not all(cur % i for i in range(ceil(sqrt(cur)), 10**n)):
return cur % 1337
return 9
Explain
该题解采用了一个从高到低构造回文数的方法。首先，对于n位数字，最大可能的数字是10^n-1。解题思路是从这个最大数开始，逐步减小，构造可能的回文数，检查它是否可以由两个n位数的乘积构成。具体做法是，对于每一个数part，将其转换为字符串，并将字符串反转后拼接到原字符串后面，形成一个回文数。然后，从sqrt(cur)开始向下检查，直到10^n，看这个回文数是否能被这些数整除，如果能，则返回该回文数对1337取余的结果。如果在所有n位数范围内找不到符合条件的回文数，最后返回9（即1位数的最大回文数，特殊情况处理）。
时间复杂度: O(10^n * sqrt(10^n))
空间复杂度: O(1)
class Solution:
def largestPalindrome(self, n: int) -> int:
if n == 1: return 9 # 特殊情况，1位数的最大回文数
for part in range(10**n-1, 10**(n-1)-1, -1):
cur = int(str(part) + str(part)[::-1]) # 构造回文数
if not all(cur % i for i in range(10**n, int(cur**0.5), -1)):
return cur % 1337 # 如果找到，返回取余结果
return 9 # 如果没有找到，返回特殊值
Explore
在给定一个n位数的定义中，n位数的范围是从`10^(n-1)`到`10^n-1`。例如，如果n=2，那么两位数的范围是从10到99。因此，`10^n`实际上是一个(n+1)位的数字，而不是n位。所以，使用`10^n-1`作为起始点，因为它是n位数字中的最大值。
检查一个数是否可以被另一个数整除，如果我们已知这个数是两个n位数字的乘积构成的回文数，最大的乘数不会超过这个回文数的平方根。这是因为，如果存在两个乘数a和b使得a*b等于这个回文数，并且a和b都大于`sqrt(cur)`，那么a*b会超过cur，这与我们的假设矛盾。因此，从`sqrt(cur)`开始向下检查到`10^(n-1)`（n位数的最小值）是足够的，这样可以节省计算时间和资源。
实际上，对于n大于1的情况，总是可以找到至少一个回文数，它是两个n位数的乘积。这是因为回文数的生成和检查涵盖了所有从`10^n-1`到`10^(n-1)`的数，这保证了我们检查了所有可能的回文数。返回9的情况主要是针对n=1的特殊情况，这是因为1位数字的最大回文数是9。对于n大于1的情况，这种情况不太可能发生，因为会有更大的回文数存在。