LeetCode 题解工作台
最大回文数乘积
给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。 示例 1： 输入： n = 2 输出： 987 解释： 99 x 91 = 9009, 9009 % 1337 = 987 示例 2： 输入： n = 1 输出： 9 提示…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数学·结合·enumeration
答案摘要
class Solution: def largestPalindrome(self, n: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·enumeration 题型思路
题目描述
给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。
示例 1：
输入：n = 2 输出：987 解释：99 x 91 = 9009, 9009 % 1337 = 987
示例 2：
输入：n = 1 输出：9
提示:
1 <= n <= 8
解题思路
方法一
class Solution:
def largestPalindrome(self, n: int) -> int:
mx = 10**n - 1
for a in range(mx, mx // 10, -1):
b = x = a
while b:
x = x * 10 + b % 10
b //= 10
t = mx
while t * t >= x:
if x % t == 0:
return x % 1337
t -= 1
return 9
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on generating palindrome candidates and verifying factor pairs, roughly O(10^n) in the worst case. Space complexity is minimal, mainly storing current palindrome candidates and temporary variables. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect efficient palindrome generation without checking all products.
- question_mark
Look for correct handling of modulo 1337 to avoid integer overflow.
- question_mark
Check understanding of factor enumeration and early termination strategies.
常见陷阱
外企场景- error
Checking every product of n-digit numbers instead of generating palindrome candidates first.
- error
Forgetting to verify that both factors are n-digit integers.
- error
Neglecting modulo 1337, causing incorrect results for large n.
进阶变体
外企场景- arrow_right_alt
Find the smallest palindrome from two n-digit numbers instead of the largest.
- arrow_right_alt
Return the largest palindrome without modulo constraints.
- arrow_right_alt
Compute the largest palindrome from three n-digit numbers using similar enumeration.