【leetcode每日一题】479. 最大回文数乘积

题目来源

点这里

题意

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

思路

开始刷leetcode每日一题的Day3。

我是真的菜，看完这个题面感觉非常懵逼。2个n位数的乘积最高可达16位数，我就在想到底是用long long，还是用数组来存。

当然，我马上就跑去看了题解。（哈哈，菜鸟的觉悟）

题解说这道题用枚举。2个n位整数的乘积，最多有2n位。因为是回文数，所以只需要知道前面一半的数，就能知道整个数的样子，所以枚举前n位整数即可（因为1<=n<=8，所以最多8位整数也不会超过int型范围）。从n位的最大数开始往下枚举，也就是从2^n-1开始枚举。对于每个回文数x，都去判断它是不是2个n位整数的乘积。这里的判断又是枚举，不过只枚举到根号下x就行。

感觉自己说的有点混乱。

代码

class Solution {
public:
    bool isN(int x,int n) { // 判断x是不是n位数
        int _n=0;
        do {
            x /= 10;
            _n++;
        }while(x>0);
        return _n==n;
    }
    int largestPalindrome(int n) {
        for(int i=pow(10,n)-1; i>=pow(10,n-1); --i) { 
        // 枚举回文数的左边n位
        // 还原回文数x
            long long x = i*pow(10,n);
            int t=0, m=i;
            do {
                t = t*10+m%10;
                m/=10;
            }while(m>0);
            x += t;
            int sqr = sqrt(x);
            // 判断x是不是两个n位数的乘积
            for(int j=pow(10,n)-1; j>=sqr; --j) {
            // j只需要枚举到根号x即可
                if(x%j==0 && isN(x/j, n)==true) { 
                // 如果x/j是n位整数，直接返回取余的结果
                    return x%1337;
                }
            }
        }
        return 9;// n=1的特例
    }
};

注意

因为这里n的范围有限，对于上面的算法只有一个特例就是n=1时。按照普遍的逻辑来说，n=1得到的回文数应该是2位数，但是很遗憾，2位数没有满足条件的。n=1时，满足条件的最大回文数是最大的个位数9。所以我把它单独提出来返回的。