目录

1. 题目描述

2. 解题分析

2.1 常规情况

2.2 输入数本身是回文数的情况

2.3 原数是非回文数的特殊情况

2.4 原数是回文数的特殊情况

2.3 综合考虑

3. 代码实现

1. 题目描述

        给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。“最近的”定义为两个整数差的绝对值最小。

示例 1:
输入: n = "123"
输出: "121"

示例 2:
输入: n = "1"
输出: "0"
解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
 
提示:

• 1 <= n.length <= 18
• n 只由数字组成
• n 不含前导 0
• n 代表在 [1, 10^18 - 1] 范围内的整数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-closest-palindrome
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

        这道题目看起来很简单，但是的确当得起“Difficult”的分级，而且在我看来是difficult中的difficult，手机中的战斗机。

2.1 常规情况

        因为是要构造距离原数最近回文数，所以相对于原数改变得越少越好。因此肯定是要优先于低位数据的改变。所以，直感的方法是从数据低位开始，依次替换为它对称位置的高位数，直到变成回文数为止。比如说，12345-->12321、1234512345-->1234554321.

2.2 输入数本身是回文数的情况

        另外，由于不能返回原数本身，所以对于已经构成了回文数的数，同样需要改变。因为本身已经是回文数，任何改动都需要对称性地修改才能不破坏对称性。而如上所述，修改的位数越低越少就越好，因此修改应该限定于中间数字的对称性修改。如果原数位数为奇数的话，则将中央数字减一（因为在存在多个解时要取较小的那个）；如果原数位数为偶数的话，则将中央两个数字各减一（因为在存在多个解时要取较小的那个）。

        对于大多数情况，结合2.1和2.2都给出了最优解。但是，如果仅仅这样就够了的话，那就只是一道simple level的题目了。

2.3 原数是非回文数的特殊情况

        比如说，921按照以上规则会得到929，事实上919更加靠近921。

        又比如说，901按照以上规则会得到909，事实上898更加靠近901。

        又比如说，199-->202, instead of 191.

2.4 原数是回文数的特殊情况

        考虑原数为回文数，如上所述，在一般情况下，将中央一个或两个数字减一即可。但是有些情况下这样行不通。但是当中央数字为0呢？

        例1：101。中央数字为0，减一后应该得到什么呢？按模10运算的话，会得到191，但是实际上正解应该是99。同样还有1001-->999、120021-->119911等。。。

        也就是当原数为回文数，而中央数字为0时，以上常规规则是不适用的。

        反过来说，当中央数字为9时，也会出现异常。比如说，99-->101 instead of 88.

2.3 综合考虑

        综上所述，按照2.1所述常规规则得到的结果并不总是最优解，可能比最优解大，也可能比最优解小。那如何将这些异常情况识别出来，又如何进行修正呢？经过几次提交尝试都没有能够覆盖所有情况后，脑袋爆炸了。。。give up。以下摘抄官解供有兴趣啃骨头的人参考^-^（老实讲，看答案也没有完全看明白）.

        构造的回文整数大于原数时，我们可以减小该回文整数的中间部分来缩小回文整数和原数的差距。例如，对于数 99321，我们将构造出回文整数 99399，实际上 99299 更接近原数。

        当我们减小构造的回文整数时，可能导致回文整数的位数变化。例如，对于数 100，我们将构造出回文整数 101，减小其中间部分将导致位数减少。得到的回文整数形如 999... 999（10^len+1）。
        构造的回文整数小于原数时，我们可以增大该回文整数的中间部分来缩小回文整数和原数的差距。例如，对于数 12399，我们将构造出回文整数 12321，实际上 12421 更接近原数。

        当我们增大构造的回文整数时，可能导致回文整数的位数变化。例如，对于数 998，我们将构造出回文整数 999，增大其中间部分将导致位数增加。得到的回文整数形如 100…001（10^len+1）。
        构造的回文整数等于原数时，由于题目约定，我们需要排除该回文整数，在其他的可能情况中寻找最近的回文整数。

        考虑到以上所有的可能，我们可以给出最终的方案：分别计算出以下每一种可能的方案对应的回文整数，在其中找到与原数最近且不等于原数的数即为答案。

• 用原数的前半部分替换后半部分得到的回文整数。
• 用原数的前半部分加一后的结果替换后半部分得到的回文整数。
• 用原数的前半部分减一后的结果替换后半部分得到的回文整数。
• 为防止位数变化导致构造的回文整数错误，因此直接构造 999…999 和 100…001 作为备选答案。

3. 代码实现

class Solution:

    def nearestPalindromic(self, n: str) -> str:
        l = len(n)
        if l == 1:
            return str(int(n) - 1)
        s = n[: l // 2 + l % 2]
        s1 = str(int(s) - 1)
        s2 = str(int(s) + 1)
        return min(
            '9' * (l - 1), 
            '1' + '0' * (l - 1) + '1',
            s + s[-1 - l % 2::-1], 
            s1 + s1[-1 - l % 2::-1], 
            s2 + s2[-1 - l % 2::-1], 
            key=lambda x: (abs(int(x) - int(n)) or 114514, int(x))
        )
    
    def nearestPalindromic(self, n: str) -> str:
        m = len(n)
        candidates = [10 ** (m - 1) - 1, 10 ** m + 1]
        selfPrefix = int(n[:(m + 1) // 2])
        for x in range(selfPrefix - 1, selfPrefix + 2):
            y = x if m % 2 == 0 else x // 10
            while y:
                x = x * 10 + y % 10
                y //= 10
            candidates.append(x)

        ans = -1
        selfNumber = int(n)
        for candidate in candidates:
            if candidate != selfNumber:
                if ans == -1 or \
                        abs(candidate - selfNumber) < abs(ans - selfNumber) or \
                        abs(candidate - selfNumber) == abs(ans - selfNumber) and candidate < ans:
                    ans = candidate
        return str(ans)

        以上包括两个解。 其中下面的是官解，另一个是其他人贡献的。只觉比官解还要神奇，一并贴在这里供仰望。。。其中甚至包含一个常数114514，不知道是什么神秘因子？

if __name__ == '__main__':        
    
    sln = Solution()  

    n = "8"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))

    n = "99"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))

    n = "100"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))

    n = "11"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))

    n = "123"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))
    
    n = "99321"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))    
    
    n = "12321"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))        
    
    n = "123321"
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed))        

    n = str(random.randint(10**18,10**19-1))    
    tStart = time.time()        
    ans = sln.nearestPalindromic(n)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(n,ans,tElapsed)) 

回到本系列总目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889