LeetCode 479 最大回文数乘积[暴力 枚举] HERODING的LeetCode之路

解题思路：
n的范围为1~8，相信大伙已经知道答案了，代码如下：

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

好了，不开玩笑了，这道题据说刚上传时是easy题，但是具有一定的难度，结果又给调成了困难题，着实给我带来了不少困惑，还以为用特别复杂的知识去解决，其实解决方法无非是枚举。

首先确定左半部分阈值，因为两个n位数乘积最大获得2n位数，所以以n位数为每个半部分，从大到小遍历（能保证是最大的回文），把获取的回文进行判断，判断是否是两个n位数整数的乘积，是直接返回回文余1337，代码如下：

class Solution {
public:
    int largestPalindrome(int n) {
        if(n == 1) return 9;
        // 获取回文左半部分阈值
        int threshold = pow(10, n) - 1;
        // 枚举回文左半部分
        for(int left = threshold; ; left --) {
            long p = left;
            // 合并整个回文
            for(int rest = left; rest > 0; rest /= 10) {
                p = p * 10 + rest % 10;
            }
            // 判断是否是两个整数的乘积
            for(long num = threshold; num * num >= p; num --) {
                if(p % num == 0) {
                    return p % 1337;
                }
            }
        }
        return 1;
    }
};