564. Find the Closest Palindrome
一道数学题。。。重点是找到各种情况并且对其简化。分成两种情况，第一种是如果S[:half] 的最后一个值 +（-1，0，1）然后翻转，第二种情况是如果要找的值和S不一样长，那么肯定是 "9...9"和“10..01”之间的一个
class Solution(object):
def nearestPalindromic(self, n):
"""
:type n: str
:rtype: str
"""
S = n
K = len(S)
candidates = [str(10**k + d) for k in (K-1, K) for d in (-1, 1)]
prefix = S[:(K+1)/2]
P = int(prefix)
for start in map(str, (P-1, P, P+1)):
candidates.append(start + (start[:-1] if K%2 else start)[::-1])
def delta(x):
return abs(int(S) - int(x))
ans = None
for cand in candidates:
if cand != S and not cand.startswith('00'):
if (ans is None or delta(cand) < delta(ans) or
delta(cand) == delta(ans) and int(cand) < int(ans)):
ans = cand
return ans
