[刷题防痴呆] 0479 - 最大回文数乘积 (Largest

题目地址

https://leetcode.com/problems/largest-palindrome-product/

题目描述

479. 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

思路

• 模拟.
• n为1, 最大为9.
• 否则, 求出能构成回文的取值范围min和max.
• 从大到小依次reverse拼接出一个备选答案.
• 然后看能否被整除.
• 如果可以整除, 则这个备选答案就是最大能构成的回文数.

关键点

代码

• 语言支持：Java

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        int mod = 1337;
        int min = (int) Math.pow(10, n - 1);
        int max = (int) (Math.pow(10, n)) - 1;
        
        for (int i = max; i >= min; i--) {
            String temp = Integer.toString(i);
            StringBuffer sb = new StringBuffer();
            sb.append(temp);
            String reverse = sb.reverse().toString();
            long product = Long.valueOf(temp + reverse);
            for (long j = max; j * j >= product; j--) {
                if (product % j == 0) {
                    return (int)(product % mod);
                }
            }
        }
        
        return -1;
    }
}