LeetCode 479. 最大回文数乘积题解

479. 最大回文数乘积题解

题目来源：479. 最大回文数乘积

2022.04.16 每日一题

LeetCode 题解持续更新中GitHub仓库地址 CSDN博客地址

今天的题目思路比较简单，我个人认为难点在于回文数字的构造之上，我们可以通过从大到小搜索回文数字，然后判断这个回文数字能否由两个 n 位整数相乘得到

这样我们就把问题分解成为两部分

• 寻找回文数字
• 判断回文数字是否由两个 n 位整数相乘得到

首先先处理简单的，判断回文数字能否由 两个 n 位数字相乘得到

我们可以将回文数开方，得到数字 s ，从 s 到 pow(10,n) 之间来寻找有没有一个数字是 此回文数的因数，如果存在，就说明这个回文数是满足我们的要求的，不存在就说明，这个回文数不是我们所要求的。

然后就是关于如何构造一个回文数字

我们根据题意可以知道，我们回文数字是由 2 个 n 位数字相乘得到，因此最多也不会超过 2*n 位数字，由此，我们可以首先确定回文数的左半部分即 n 位数字，而后再翻转，得到右半部分的数字，就组合成了一个回文数字

class Solution {
public:
    int largestPalindrome(int n) {
        // 如果 n 等于 1 直接返回 9 就行
        if (n == 1) return 9;
        // 取得 n 位数字的最大值
        int ll = pow(10, n) - 1;
        // 从最大值开始构造回文数字
        for (int l = ll;; l--) {
            // 创建回文数字变量 h ，
            // 使用 long 定义是因为会 超出 int 的范围
            long h = l;
            // 将 数字左侧的数字，逐步添加到 h 的后面
            for (int q = l; q > 0; q /= 10) h = h * 10 + q % 10;
            // 从 n 位数字的最大值开始寻找 回文数的因数
            // 如果两个的数字的乘积小于了 当前的回文数字，
            // 说明以及查找到的数字的后面的数字也不会整除此回文数
            for (long q = ll; q * q >= h; q--)
                // 如果发现了 可以整除的 数字，直接进行返回即可
                if (h % q == 0) return (int) (h % 1337);
        }
    }
};

class Solution {
    public int largestPalindrome(int n) {
        // 如果 n 等于 1 直接返回 9 就行
        if (n == 1) return 9;
        // 取得 n 位数字的最大值
        int ll = (int) Math.pow(10, n) - 1;
        // 从最大值开始构造回文数字
        for (int l = ll; ; l--) {
            // 创建回文数字变量 h ，
            // 使用 long 定义是因为会 超出 int 的范围
            long h = l;
            // 将 数字左侧的数字，逐步添加到 h 的后面
            for (int q = l; q > 0; q /= 10) h = h * 10 + q % 10;
            // 从 n 位数字的最大值开始寻找 回文数的因数
            // 如果两个的数字的乘积小于了 当前的回文数字，
            // 说明以及查找到的数字的后面的数字也不会整除此回文数
            for (long q = ll; q * q >= h; q--)
                // 如果发现了 可以整除的 数字，直接进行返回即可
                if (h % q == 0) return (int) (h % 1337);
        }
    }
}

常规方法说完了以后就来点不常规的 手动狗头

{9, 987, 123, 597, 677, 1218, 877, 475}