题目要求我们给定一个整数
n
，返回由两个
n
位数相乘得到的最大回文数。注意，因为回文数可能非常大，所以最后的结果需要对1337取余。
先来复习一下什么是回文数：回文数就是正着读和反着读都一样的数。比如
12321
、
9009
都是回文数。
显然，回文数就是一种对称的数，而我们要做的就是找出最大可能的回文数。这里有两个点需要注意：
-
如何找最大回文数
：通过两个
n
位数相乘得到回文数。我们知道，越大的数乘积肯定越大，所以我们要尽可能用尽可能大的数来做乘法。
-
如何快速判断回文数
：我们可以将乘积转换为字符串，然后判断字符串是否为回文。
首先，回文数的乘积显然是一个两数相乘的结果。为了找到最大回文数，我们可以从最大的
n
位数开始，通过两两相乘逐步找到最大的回文数。并且，这个回文数必须符合题目要求，即取余1337。
我们可以采用一个简单的暴力方法，先从最大值开始，逐个尝试每一对
n
位数的乘积，然后判断是否为回文数。具体步骤如下：
-
设定两个
n
位数的最大值为
10^n - 1
，最小值为
10^(n-1)
。
-
从最大的
n
位数开始，向下遍历每一对数，计算它们的乘积。
-
判断这个乘积是否是回文数，如果是，就记录下当前回文数。
-
最终，我们将返回的结果对1337取余。
下面是用Java实现这个算法的代码：
public class Solution {
public int largestPalindrome(int n) {
// 对于n为1的情况，我们单独处理
if (n == 1) {
return 9;
}
// 最大的n位数
int max = (int) Math.pow(10, n) - 1;
// 最小的n位数
int min = (int) Math.pow(10, n - 1);
for (int i = max; i >= min; i--) {
// 计算当前回文数的可能值
long leftPart = i;
long rightPart = i;
// 构造回文数
long palindrome = createPalindrome(leftPart, rightPart);
// 对回文数进行检查
if (palindrome continue; // 乘积大于当前回文数，直接跳过
}
// 判断这个回文数是否是一个乘积
for (int j = max; j >= min; j--) {
if (palindrome % j == 0 && palindrome / j <= max) {
return (int) (palindrome % 1337);
}
}
}
return 0;
}
// 构造回文数的方法
private long createPalindrome(long left, long right) {
// 将左边部分与右边反转部分组合成一个回文数
String rightStr = new StringBuilder(String.valueOf(left)).reverse().toString();
return Long.parseLong(left + rightStr);
}
}
代码解释
-
最大值和最小值
：我们首先计算出给定
n
位数的最大值和最小值。
-
回文数生成
：对于每一个可能的
n
位数，我们通过将其反转生成回文数。比如，对于
i = 123
，我们会生成
123321
这样的回文数。
-
回文数验证
：我们计算出回文数后，检查它是否能通过两个
n
位数的乘积得到。如果可以，我们返回该回文数对1337的余数。
-
优化
：一旦我们发现一个回文数，我们就跳过那些不可能为回文数的乘积，这样可以减少不必要的计算。
时间复杂度分析
由于我们从最大的
n
位数开始向下遍历，所以时间复杂度大致是 O(n^2)，不过由于通过回文数生成的方式和除法检查的优化，实际效率要高很多。
这道题通过巧妙地结合回文数的性质和暴力搜索，使我们能够在较短的时间内找到最大的回文数，并对其进行取余操作。虽然看似简单，但细节处理得当，能够有效提升算法的效率。
最后，我为大家打造了一份deepseek的入门到精通教程，完全免费：
https://www.songshuhezi.com/deepseek
同时，也可以看我写的这篇文章《
