564.md

564 Find the Closest Palindrome

Description

link

---

Solution

思路：

求出部分有可能的候选回文项，求出其中和n最近的即可

• 10...01 or 9...9 一直都是候选项
• 无论如何 动n的后半段一定比前半段来的绝对值少
• 对于n来说，如果要产生回文，一定是中间的数字不动或者在大1和小1的范围内变化

---

Code

O(n)

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        # based on @awice and @o_sharp
        l = len(n)
        # with different digits width, it must be either 10...01 or 9...9
        candidates = set((str(10 ** l + 1), str(10 ** (l - 1) - 1)))
        # the closest must be in middle digit +1, 0, -1, then flip left to right
        prefix = int(n[:(l + 1)//2])
        for i in map(str, (prefix - 1, prefix, prefix + 1)):
            candidates.add(i + [i, i[:-1]][l & 1][::-1])
        candidates.discard(n)
        return min(candidates, key=lambda x: (abs(int(x) - int(n)), int(x)))