最大回文数乘积

题目描述：

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

示例 1:

输入：n = 2
输出：987
解释：99 x 91 = 9009, 9009 % 1337 = 987
示例 2:

输入： n = 1
输出： 9

提示:

1 <= n <= 8
通过次数11,300提交次数19,314

思路:

时间复杂度：O(),空间复杂度O()

有技巧的暴力，回文数只需要知道半边就行，从大到小然后判断这个回文数是否能够被整除，如果整除就说明是答案。

代码:

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
            }
        }
    }
}

代码效率：

执行用时：84 ms, 在所有 Go 提交中击败了90.91%的用户
内存消耗：1.9 MB, 在所有 Go 提交中击败了63.64%的用户