Wednesday, November 22, 2017

[LeetCode]Largest Palindrome Product

这道题并不像题目标注的一样是easy难度的题目,之前我一直认为可能有巧妙的数学解法。结果我们还是得从最大的palindrome开始一个一个验证是不是可以表示成两个n digits数字的乘积。我们就采取这种解法,我们从大到小遍历所有的回文然后验证。值得注意的一点事,对于n位数和n位数相乘,其结果可能是2 * n - 1位数或者是2 * n位数。这里我们只验证所有的2 * n位数,理论上我们需要也验证2 * n - 1位数,但是这里除了1位数之外,2-8位数最大回文乘积都为2 * n位数,所以为了简化代码,我们只验证2 * n位数,如果想加上2 * n - 1位数验证的代码也很简单,两者非常相似。对于每一个回文palin,我们需要验证其是否能表示为两个n位数的乘积,我们这里也不需要一个一个遍历,假设最大n位数为max,最小为min。首先如果当前数i,满足palin / i > maxNum的时候我们就可以截断了,因为剩下的数肯定需要大于maxNum的数相乘才能等于palin,这是无法满足的。并且我们只需要验证所有大于等于sqrt(palin)的数。我们需要遍历10 ^ n个数(我们只需要遍历palin的前一半),并且对于每个数num,我们要sqrt(num)的时间验证,时间复杂度为O((10 ^ n) * (10 ^ 2n) ^ 0.5),代码如下;



class Solution {
public:
int largestPalindrome(int n) {
long long minNum = static_cast<long>(pow(10, n - 1)), maxNum = static_cast<long>(pow(10, n) - 1), div = static_cast<long>(pow(10, n));
//get first half of palindrome
long long lo = minNum * minNum / (div / 10), hi = maxNum * maxNum / div;
if (n == 1)return 9;
while (hi >= lo)
{
long long palin = getPalindrome(hi);
for (long long i = maxNum; i >= minNum; --i)
{
//no reason to check the number less than palin / maxNum or sqrt(palin)
if(palin / i > maxNum || i * i < palin)break;
if (!(palin % i))
return palin % 1337;
}
--hi;
}
return -1;
}
private:
long long getPalindrome(long long num)
{
long n = num, rev = 0;
while (n)
{
long digit = n % 10;
rev = rev * 10 + digit;
n /= 10;
num *= 10;
}
return num + rev;
}
};

No comments:

Post a Comment