[LeetCode]Find the Closest Palindrome

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论