LeetCode 479. 最大回文数乘积

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

英文题面：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.

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Input: n = 1
Output: 9

• 1 <= n <= 8

这题是一个比较玄学的问题，它其实是一个暴力枚举 。 但是它的这个时间复杂度虽然看似很高，但是这道题目本身就是一个暴力，虽然最坏时间复杂度很高，但是我们通过实际操作却发现答案很快就可以算出来，是这样的一种题。我们先看这道题是什么意思：给我们一个n， 让我们找一下所有由两个n位数组成乘积的数里面最大的一个回文数是多少？

这个n位数是什么呢？比如当三位数n=3的时候就是100～999里面所有两个三位数的乘积里面最大的一个回文数是多少；当两位数n=2的时候就是10～99里面所有两个两位数的乘积里面最大的一个回文数是多少，样例给出了是99 x 91 = 9009，最后返回的这个最大的回文数根据题目的要求模上1337就是答案987。

这种题的输入范围是很小的所以可以直接打表，在力扣的评测机里面直接输入1～9就可以评测出答案{9,987,123,597,677,1218,877,475}，最后根据要求直接返回即可。注意考试的时候打表没有问题，但是在面试的时候如果遇到面试官不允许的话就无法打表了。

那这题该怎么做呢？这题可能有同学会想有没有能够优化的做法，答案是没有的，我们直接暴力去做就可以了。因为大家试过一遍就可以发现答案其实很快就可以找到（虽然他的时间复杂度很大，但是巧在他的答案都分布在遍历刚开始没多久的区域，所以我们很快就可以得到答案，所以说这题很玄学，但是这题根据网上的信息在面试中很少遇到，所以大家图一乐就好）。

首先枚举的时候我们得想一下怎么暴力，你不能写那种一看就会超时的暴力（比如从小往大枚举，也不剪去绝对不正确的情况一直枚举到最大，相信很多科班的同学第一次优化暴力枚举是在谭浩强的c语言程序设计上面求质数的那道题吧，与这道题有异曲同工之妙），又或者是枚举两个数然后去判断它的回文串的话这种就比较慢了，可能会超时。那么这题我们这么枚举呢，也就是这题出题的精髓和本质，就是从大到小去枚举回文数，从大到小枚举回文数的话其实只需要枚举一半就可以了。为什么只需要枚举一半就可以了呢，因为回文数左右两边其实是一样的，枚举左边右边就有了，所以我们这题其实是枚举回文数，从大到小枚举回文数其实就是从大到小枚举答案。比如说等于3的时候，就是从999999开始枚举，判断一下这个数能不能整除一下999并且整除之后的这个数也是n位数，如果是的话就成功了，反之就失败了继续枚举下一个数998899能不能分成两个n位数相乘，我们同样从999开始，这里需要注意的是我们必须保证999的平方必须大于等于998899才可以，因为如果小于998899的话那么就意味着我们另外一个数必然不是三位数，所以我们从最大数开始枚举的时候我们要求999的平方必须要大于等于998899才行。这样的话其实就是相当于我们每次枚举较大的那个数，因为两个数相乘，n如果可以分成两个n位数相乘的话（假设为a和b且a大于等于b），那么a和b其实是没有顺序的是吧，但是我们每次枚举的是枚举较大的那个数也就是枚举a，此时有a^2>=a*b=n也就是a的平方要大于等于n。

所以我们再去做的时候要求：

• 最大数开始枚举
• n位数最大数的平方一定要大于等于我们枚举的这个数

然后这里面的边界问题，就是说两个n位数相乘的话它得到的数不一定是2n位也有可能是2n-1位，比如说100✖️100=10000是五位数，但是999✖️999=998001这个就是是一个六位数，经过实验可以发现在2～8的范围内，最大数字必定是2n位，所以在2n位数里面一定是有答案的。如果n=1的话口算一下只有3的平方等于9，所以特判一下n=1的情况就可以了，所以这题就暴力去做。还是那句经典的话，虽然看似这道题目的暴力的情况下跟慢，但是其实很快就可以找到答案。然后是代码实现：

class Solution {
public:
    int largestPalindrome(int n) {
        typedef long long LL;
        if(n==1) return 9;
        int maxv=pow(10,n)-1;
        for(int i=maxv;;i--) {
            auto a=to_string(i);
            auto b=a;
            reverse(b.begin(),b.end());
            auto num=stoll(a+b);
            for(LL j=maxv;j*j>=num;j--) {
                if(num%j==0) 
                    return num%1337;
            }
        }
        // return 0;
    }
};

func largestPalindrome(n int) int {
    if n == 1 {
        return 9
    }
    upper := int(math.Pow10(n)) - 1
    for left := upper; ; left-- { // 枚举回文数的左半部分
        p := left
        for x := left; x > 0; x /= 10 {
            p = p*10 + x%10 // 翻转左半部分到其自身末尾，构造回文数 p
        }
        for x := upper; x*x >= p; x-- {
            if p%x == 0 { // x 是 p 的因子
                return p % 1337
            }
        }
    }
}

时间复杂度：$O(10^{2n})$。枚举left 和 x 的时间复杂度均为 $O(10^{2n})$ 。实际上我们只需要枚举远小于$O(10^{2n})$ 个的left 就能找到答案，实际的时间复杂度远低于$O(10^{2n})$。

空间复杂度：O(1)，我们只需要常数的空间保存若干变量。

最后提供文中提到过的有趣的打表的方法的程序实现：

class Solution {
public:
    int largestPalindrome(int n) {
        vector<int> ans = {9,987,123,597,677,1218,877,475};
        return ans[n-1];
    }
};