479-最大回文数乘积

479-最大回文数乘积

题目描述： 给定一个整数 n ，返回 *可表示为两个 n 位整数乘积的最大回文整数 。因为答案可能非常大，所以返回它对 1337取余 。

示例1：

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

示例2：

输入： n = 1
输出： 9

提示：

• 1 <= n <= 8

思路：

• 首先要知道什么是回文数，回文数即，正序和反序一样的数字。例如：
  • 1001、9999、999 等都是回文数
  • 10、1000、10100 等不是回文数
• 首先我们应该知道，如果输入的数字为n，那么两个 n 位数乘积位数最大为 2n，且回文数左右两部分应该是对称，即从 10 ^ n - 1 开始枚举左半部分就可以了。
• 详细步骤参照代码讲解。

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        // 定义一个常量upper用以定义两个n位数相乘最大的数
        int upper = (int) Math.pow(10, n) - 1;
        // 定义一个常量ans 用以保存答案
        int ans = 0;
        // 外层 for 循环，判断条件为 ans 是否找到，因为从大到小遍历，所以找到即为最大回文子串
        for (int left = upper; ans == 0; --left) { // 枚举回文数的左半部分
            // 定义long型常量，用以保存两个n位整数相乘得出的数据
            long p = left;
            // 第一个内层 for 循环，用于找 2n 位整数的回文数
            // 例如：
            // 99 回文数是 9999
            // 98 回文数是 9889
            // 97 回文数是 9779
            for (int x = left; x > 0; x /= 10) {
                p = p * 10 + x % 10; // 翻转左半部分到其自身末尾，构造回文数 p
            }
            // 第二个内层 for 循环，用于判断 p 能否被一个 n 位整数整除
            for (long x = upper; x * x >= p; --x) {
                // 如果 if 判断为true，即上一个内存 for 循环找到的值可以被一个 n 位整数整除
                // 即 p 是符合题意的值
                if (p % x == 0) { // x 是 p 的因子
                    // 若 p 过大，则对1337取模并作为答案返回。
                    ans = (int) (p % 1337);
                    break;
                }
            }
        }
        return ans;
    }
}