题目描述：

LeetCode 564. Find the Closest Palindrome

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Example 1:

Input: "123"
Output: "121"

Note:

1. The input n is a positive integer represented by string, whose length will not exceed 18.
2. If there is a tie, return the smaller one as answer.

题目大意：

给定整数n，寻找距离n最近（不包含n）的回文数。两个整数的距离是指其差的绝对值。

注意：

1. n是字符串表示的正整数，长度不超过18。
2. 如果距离相等，返回值较小的整数。

解题思路：

记n的前半部分为p，分别用p，p - 1，p + 1及其逆序串拼接成长度为奇数或者偶数的回文串。

假设n的长度为m， p的长度应分别取m / 2，m / 2 + 1。

另外需要考虑进位时的边界情况，比如测试用例：11, 1001, 999

Python代码：

class Solution(object):
    def nearestPalindromic(self, n):
        """
        :type n: str
        :rtype: str
        """
        evenPal = lambda sp : int(sp + sp[::-1])
        oddPal = lambda sp : int(sp + sp[::-1][1:])
        sn, n = n, int(n)
        if len(sn) == 1: return str(n - 1)
        ans = -999999999999999999
        mid = len(sn) / 2
        for sp in sn[:mid], sn[:mid + 1], str(int(sn[:mid]) * 10):
            p = int(sp)
            for pal in evenPal, oddPal:
                for d in -1, 0, 1:
                    val = pal(str(p + d))
                    if val == n: continue
                    ans = min(ans, val, key = lambda x : (abs(x - n), x))
        return str(ans)

 

本文链接：http://bookshadow.com/weblog/2017/04/23/leetcode-find-the-closest-palindrome/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码