479. 最大回文数乘积

题目

给定一个整数 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

从大值开始枚举回文数，判断是否可以拆成两个n位数乘积。

比如，n=2，最大的两位数为99，从99开始构造回文数，左边为99时右边也是99，回文为9999，不过其大于，因此跳过。继续看98，回文数为9889，也大于，跳过。再看97，9779不超过，但是无法表示为两个两位数乘积，继续看96,95,…，直至找到一个可以拆成两个n位数的回文数。

代码

class Solution {
    public int largestPalindrome(int n) {
        // n为1时，不适用下面的算法，单独返回
        if (n == 1) {
            return 9;
        }
        int k = (int) Math.pow(10, n) - 1;
        // 枚举回文左半部分，对应代码中的i
        for (int i = k; i >= 1; i--) {
            long pal = i;
            int tmp = i;
            while (tmp > 0) {
                pal = pal * 10 + tmp % 10;
                tmp /= 10;
            }
            // 回文数不可以超过k的平方
            if (pal > (long) k * k) {
                continue;
            }
            // 判断pal是否可以拆成两个n位数乘积，因子从k开始，另一个因子一定小于k
            for (long j = k; j * j >= pal; j--) {
                if (pal % j == 0) {
                    return (int) (pal % 1337);
                }
            }
        }
        return -1;
    }
}