从Leetcode 每日一题练习继续讨论：
564. 寻找最近的回文数
564. Find the Closest Palindrome
题解
本题考虑能得到离一个数最近的回文数的所有情况, 假设数字根据长度中间位置有一个"对称轴". 则在对称轴两侧的数字完全按逆序排列即得到回文数, 从原始数字得到回文数可以直接复制左半边的数字并逆序, 可以将左半边数字加一并逆序, 也可以将左半边数字减一并逆序. 只需要比较这几种情况得到的回文数哪个和原数字的差最小即可. 但除此以外还要考虑如999这样的数字, 距离其最近的回文数为1001, 同样对于1000来说, 其对应的回文数为999, 因此需要将这两种情况也考虑在内. 因此对于任意数字, 列举这五种情况下得到的回文数并选择与原数字差最小的即可. 注意对于本身已经是回文数的不能选择自身, 即差必须大于0.
代码
func nearestPalindromic(n string) string {
num, _ := strconv.Atoi(n)
length := len(n)
candidates := []int{}
// 情况1：999 -> 1001
candidates = append(candidates, int(math.Pow10(length)) + 1)
// 情况2：1000 -> 999
candidates = append(candidates, int(math.Pow10(length-1)) - 1)
// 获取左半部分
leftHalf := n[:(length+1)/2]
leftNum, _ := strconv.Atoi(leftHalf)
// 情况3：直接镜像
candidates = append(candidates, createPalindrome(leftNum, length%2 == 0))
// 情况4：左半部分+1
candidates = append(candidates, createPalindrome(leftNum+1, length%2 == 0))
// 情况5：左半部分-1
candidates = append(candidates, createPalindrome(leftNum-1, length%2 == 0))
closest := candidates[0]
minDiff := abs(num - closest)
for _, candidate := range candidates[1:] {
diff := abs(num - candidate)
if (diff < minDiff && diff > 0) || (diff == minDiff && candidate < closest) {
closest = candidate
minDiff = diff
}
}
return strconv.Itoa(closest)
}
func createPalindrome(num int, even bool) int {
palindrome := num
if !even {
num /= 10
}
for num > 0 {
palindrome = palindrome*10 + num%10
num /= 10
}
return palindrome
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}