新浪博客

最大回文数乘积（力扣网）

2022-04-16 17:46阅读：

http://blog.sina.cn/dpool/blog/u/5751332021

给定一个整数 n ，返回 可表示为两个 n 位整数乘积的 最大回文整数 。因为答案可能非常大，所以返回它对 1337 取余 。
示例 1:
输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987
示例 2:
输入： n = 1
输出： 9
提示:
1 <= n <= 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-palindrome-product
此题描述很简单，但难道不小，先不说别的，10^8相乘，那是16个零，js的正常计算方式肯定溢出。
下面说说我一开始的思路，一开始，我的思路是比较简单的，找规律，找到一个通用的规律，本来我是个人认为，应该是n位9乘上某个数字得到的回文串，所以一直沉浸于此，发现n为双数，可以得到结果，单数结果是undefined，所以我的思路有问题。
所以，又是我的制胜法宝-观摩他人解题思路，
先上代码：
var largestPalindrome = function(n){

if(n==1)return 9;
var cutVal = Math.pow(10,n
) -1;

for(var left = cutVal; left > cutVal/10;left--){
var right = left.toString().split('').reverse().join('');
var val =BigInt(left+ '' +right);
var x =BigInt(cutVal);
while(x*x>= val){
if(val% x ==BigInt(0)){
console.log(x,val/x);
return val %BigInt(1337);
}
x--;
}
}
};
看着代码是不是很简短。
那我就开始说说思路：
首先一点，输入整数 n ，那么乘积的最大值小于 Math.pow(10,n)*Math.pow(10,n)，这里是极限。
极限找到了，这里要找最大的，是不是就从最大乘积往下找。
不过这样子遍历找是肯定不行的，位数太大。
那么就要简化。
首先是位数，大家想想，比如n=3，最长是6位，我们将6位数平均分成left，right两部分，左右肯定是对称的，即right= left.toString().split('').reverse().join(''); 回文串就是 val = left + ' ' +right;（如果是纯数字的字符串相加，会视为数字相加，不是字符串拼接）
到这里，是不是有思路了，遍历left，从大到小，一一拼接出回文串，然后判断这个回文串能不能被整除。
这个寻找被整除的数，不也是从大到小么，即从x = cutVal开始往下找，不过前提是 x*x>=val，（这个条件不懂的可以思考一下，想想这个遍历的过程，是从大到小的）
这个遍历的过程，如果 val%x==0，说明符合条件，做取余返回即可

我的更多文章

下载客户端阅读体验更佳

APP专享