寻找最近的回文数

题目描述：

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: n = “123”
输出: “121”
示例 2:

输入: n = “1”
输出: “0”
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。

提示:

1 <= n.length <= 18
n 只由数字组成
n 不含前导 0
n 代表在 [1, 1018 - 1] 范围内的整数
通过次数11,931提交次数45,674

思路:

例如对于 abcdeabcde 来说，最近的回文数值的前三位可能是 abcabc、abc+1abc+1 和 abc-1abc−1 三者之一，其他位置的数值随着前三位的确定而唯一确定。还有特殊的情况得9999和10001里面选一个最接近的数。

代码:

import "strconv"
func nearestPalindromic(n string) string {
    m := len(n)
    if m == 1{
        return string(n[0]-1)
    }
    candidates := []int{int(math.Pow10(m-1)) - 1, int(math.Pow10(m)) + 1}
    selfPrefix, _ := strconv.Atoi(n[:(m+1)/2])
    for _,x := range []int{selfPrefix,selfPrefix+1,selfPrefix-1} {
        y := x
        if m % 2 == 1{
            y /= 10
        }
        for ;y>0;y/=10{
            x = x*10 + y %10
        }
        candidates = append(candidates, x)
    }
    ans := -1
    num,_ := strconv.Atoi(n)
    for _,x := range candidates{
        if x != num && (ans == -1 ||  abs(ans-num) > abs(x - num) || (abs(ans-num) == abs(x - num) && x < ans)) {
            ans = x
        }
    }
    return strconv.Itoa(ans)

}

func abs(n int)int{
    if n <0{
        return -n
    }
    return n
}

代码效率：

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