原文链接: https://leetcode-cn.com/problems/largest-palindrome-product

英文原文

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

 

Example 1:

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:

Input: n = 1
Output: 9

 

Constraints:

• 1 <= n <= 8

中文题目

你需要找到由两个 n 位数的乘积组成的最大回文数。

由于结果会很大，你只需返回最大回文数 mod 1337得到的结果。

示例:

输入: 2

输出: 987

解释: 99 x 91 = 9009, 9009 % 1337 = 987

说明:

n 的取值范围为 [1,8]。

通过代码

高赞题解

参考了国际版leetcode的讨论区解法

核心思想：由大到小构造一个回文数，然后看这个回文数是否能由给定的数相乘得到。

• 第一个循环为什么从max - 1开始？
  9x9 = 81
  99x99 = 9801
  999x999 = 998001
  9999x9999 = 9980001
  etc.
  可以看出， max * max 得到的数一定不是回文数，所以从max - 1开始循环
• 如何判断构造的回文数能够由给定的数相乘得到？
  看回文数能否被给定的数之一整除
• 举个例子：
  max = 99;
  从i= 98开始循环
  构造出回文数 rev = 9889
  对于 x = 99 ，rev不能整除，继续
  对于 x = 98 , 98 * 98 = 9604,小于rev，退出第二层循环
  …
  …
  直到i= 90
  构造出回文数9009
  对于x = 99 ， 整除，得到结果

class Solution {
    public int largestPalindrome(int n) {
        if(n == 1) return 9;
        //计算给定位数的最大值
        long max = (long)Math.pow(10,n) - 1;
        //从max - 1开始循环，原因见上文
        for(long i = max - 1; i > max / 10; i--){
            //1. 构造回文数
            String s1 = String.valueOf(i);
            long rev = Long.parseLong(s1 + new StringBuilder(s1).reverse().toString());
            //2. 检验该回文数能否由给定的数相乘得到
            for(long x = max; x * x >= rev; x --){
                if(rev % x == 0) return (int)(rev % 1337);
            }
        }
        return -1;
    }
}

统计信息

通过次数	提交次数	AC比率
3249	7610	42.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言