[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)，代码如下;