564 寻找最近的回文数（脑筋急转弯）

古城微笑少年丶 2022-08-31 09:45 245阅读 0赞

**1. 问题描述：**

给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。"最近的"定义为两个整数差的绝对值最小。

**示例 1:**

输入: "123"  
输出: "121"

**注意:**

n 是由字符串表示的正整数，其长度不超过18。  
如果有多个结果，返回最小的那个。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-the-closest-palindrome

**2. 思路分析：**

这道题目属于**脑筋急转弯**的题目，我们可以先从具体的例子找一下规律。如果数字n为回文串那么当我们确定它的前一半的数字之后那么后一半数字也确定了，对于当前的数字n我们可以考虑三种情况，我们可以从具体的例子考虑，例如n = 12345；当n的前三位确定的时候，也即前三位为m = 123，这个时候由m确定的回文数应该是离n比较近的，此时对应的回文数为12321；第二种情况是比m小一点三位数为m = 122，由m确定的回文数为12221；第三种情况是比m大的三位数为m = 124，由m确定的回文数为12421，所以离n最近的三个回文数为12221 < 12321 < 12421，并且可以发现他们之间是没有任何其他的回文数的；对于当前的数字n长度为t的时候也是一样的，也需要确定n的前半部分的数字，上面是普遍的情况，我们还需要考虑一下某些特殊的情况，例如n = 999，通过上面的方法计算得到左边的数为989，右边的数为100001，而右边的数虽然是回文数但是不是离999最近的，离n最近的回文数为1001，所以对于这两种情况我们需要特判一下，最终我们需要在这五个数中选出一个离n最近的回文数即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

import math
    
    
    class Solution:
        def nearestPalindromic(self, num: str) -> str:
            n = len(num)
            S = list()
            # 先将两个边界插入到列表中, 例如n = 999等若干个9的情况
            S.append(int(math.pow(10, n - 1) - 1))
            S.append(int(math.pow(10, n) + 1))
            # m为当前num中前半部分, 这里需要注意加(n + 1) // 2这样长度为奇数的时候截取的也是中间的那一部分
            m = int(num[:(n + 1) // 2])
            # 确定n的前半部分之后得到对应的回文数
            for i in range(m - 1, m + 2):
                a = str(i)
                # 翻转一下a得到另一半回文数
                b = a[::-1]
                t = 0
                # 这里需要判断一下n的长度是奇数还是偶数
                if n % 2 == 0:
                    t = int(a + b)
                else:
                    # 奇数的话那么中间那个字符不应该重复计算所以需要从第一位开始截取
                    t = int(a + b[1:])
                S.append(int(t))
            res = int(2 * math.pow(10, 18))
            # 因为有可能存在多个答案题目要求输出最小的那个所以需要先排序
            S.sort()
            k = int(num)
            # 枚举答案
            for x in S:
                # 注意答案不能够是自己
                if abs(x - k) < abs(res - k) and x != k: res = x
            return str(res)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/fd6f5c0d91df4947962ed9be6e565b19.png