Skip to content

Latest commit

 

History

History
121 lines (75 loc) · 3.59 KB

0564._Find_the_Closest_Palindrome.md

File metadata and controls

121 lines (75 loc) · 3.59 KB

564. Find the Closest Palindrome

难度: Hard

刷题内容

原题连接

内容描述

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:
The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.

解题方案

思路 1 - 时间复杂度: O(len(n))- 空间复杂度: O(1)******

前前后后搞了2天，感谢今天下午女朋友和我一起讨论，最终搞出来了。

  • 总共三种情况，算出后面的，前面的，还有当前的前半部分直接反转黏贴到后半部分。总结一下就是说 {前半部分+1，前半部分-1,前半部分自身} + 前面得出结果的反转就是我们可能的结果之一。
  • 另外两种情况就是进位和减位，格式为1000..0001, 999...999

5个部分看看哪个更近，唯一需要注意的是输入为10和11的时候handle不了，要在最前面手动处理一下。

beats 100%，功夫不负有心人！

class Solution(object):
    def nearestPalindromic(self, n):
        """
        :type n: str
        :rtype: str
        """
        tmp = str(n)
        if 9 < int(n) < 12:
            return '9'
        r_half_len = len(tmp) // 2
        if len(tmp) & 1 == 0: # 长度为偶数
            num_digits = len(str(int(tmp[:len(tmp)/2]))) 
            half = tmp[:len(tmp)/2]
        else:                 # 长度为奇数
            num_digits = len(str(int(tmp[:(len(tmp)+1)/2])))
            half = tmp[:(len(tmp)+1)/2]
            
        if len(str(int(half)+1)) > num_digits: # 进位了
            behind = '1' + '0' * (len(tmp)-1) + '1'
        else:
            behind = str(int(half) + 1)+ str(int(half) + 1)[:r_half_len][::-1]
        if len(str(int(half)-1)) < num_digits: # 减位了
            before = '9' * (len(tmp)-1)
        else:
            before = str(int(half) - 1)+ str(int(half) - 1)[:r_half_len][::-1]
        # 当前的前半部分直接反转，如1002，变成了1001
        cur = str(int(half))+ str(int(half))[:r_half_len][::-1] 
        if cur == tmp[::-1]:
            return behind if abs(int(tmp)-int(behind)) < abs(int(tmp)-int(before)) else before
        abss = map(lambda x: abs(int(x)-int(tmp)), [before, cur, behind])
        selects = [before, cur, behind]
        return selects[abss.index(min(abss))]

思路 2 - 时间复杂度: O(len(n))- 空间复杂度: O(1)******

后面我觉得完全可以重构一下代码，behind和before不用非得算出来，我只要把所有的可能性全都放到一个list里面去，最后来判断就行了

class Solution(object):
    def nearestPalindromic(self, n):
        """
        :type n: str
        :rtype: str
        """       
        prefix = int(n[:(len(n)+1)//2])
            
        candidates = set(['1' + '0' * (len(n)-1) + '1', '9' * (len(n)-1)]) # 进位减位可能性
        
        for i in map(str, [prefix-1, prefix, prefix+1]): # 前半部分+1，-1，+0可能性
            candidates.add(i + [i, i[:-1]][len(n) & 1][::-1])
            
        candidates.discard(n) # 除去自身可能就是Palindrome的可能性
        candidates.discard('') # 输入n为个位数的话，我们还会加入空字符串，必须要去掉
        
        return min(candidates, key = lambda x: (abs(int(x) - int(n)), int(x)))