目录

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、-->.

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、-->等。。。

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

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

2.3 综合考虑

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

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

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

• 用原数的前半部分替换后半部分得到的回文整数。
• 用原数的前半部分加一后的结果替换后半部分得到的回文整数。
• 用原数的前半部分减一后的结果替换后半部分得到的回文整数。
• 为防止位数变化导致构造的回文整数错误，因此直接构造 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 , 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)

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

讯享网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 = "" 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(1018,1019-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/