LeetCode刷题实战479：最大回文数乘积-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大回文数乘积，我们先来看题面：

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.

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

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

示例

示例:

输入: 2
输出: 987
解释: 99 x 91 = 9009, 9009 % 1337 = 987

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

解题

举个例子：

max = 99;

从i= 98开始循环

构造出回文数 rev = 9889

对于 x = 99 ，rev不能整除，继续

对于 x = 98 , 98 * 98 = 9604,小于rev，退出第二层循环

...

直到i= 90

构造出回文数9009

class Solution {
      public int largestPalindrome(int n) {
        if(n == 1) return 9; 
        long max = (long)Math.pow(10,n) - 1; 
        for(long i = max - 1; i > max / 10; i--){ 
            String s1 = String.valueOf(i);
            long rev = Long.parseLong(s1 + new StringBuilder(s1).reverse().toString()); 
            for(long x = max; x * x >= rev; x --){
                if(rev % x == 0) return (int)(rev % 1337);
            }
        }
        return -1;
    }
}