难度: Hard
给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: n = "123" 输出: "121"
示例 2:
输入: n = "1" 输出: "0" 解释: 0 和 2是最近的回文，但我们返回最小的，也就是 0。
提示:
1 <= n.length <= 18n只由数字组成n不含前导 0n代表在[1, 1018 - 1]范围内的整数
Submission
运行时间: 25 ms
内存: 15.9 MB
class Solution:
def nearestPalindromic(self, n: str) -> str:
length, int_n = len(n), int(n)
if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)
if int_n - 1 == 10 ** (length-1): return str(int_n-2)
if int_n + 1 == 10 ** length: return str(int_n + 2)
pre = int(n[:(length+1)//2])
tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]
return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))
Explain
题解思路主要分为几个步骤：1. 特殊情况处理：如果n小于10或者n等于10的幂次方，则直接返回n-1；如果n减1等于10的幂次方，则返回n-2；如果n加1等于10的下一个幂次方，则返回n+2。这些特殊情况处理主要是为了应对边界情况。2. 对于一般情况，先找到n的前半部分（对于奇数长度的n，中间的数字也包括在前半部分），然后构造三个候选的回文数，分别是将前半部分减1、不变、加1后，再将其翻转拼接到后半部分。3. 在这三个候选回文数中，找出与n差的绝对值最小的那个，如果有多个差值相同的，则返回较小的那个。
时间复杂度: O(length)
空间复杂度: O(length)
class Solution:
def nearestPalindromic(self, n: str) -> str:
length, int_n = len(n), int(n)
# 特殊情况处理
if int_n < 10 or int_n == 10 ** (length-1): return str(int_n-1)
if int_n - 1 == 10 ** (length-1): return str(int_n-2)
if int_n + 1 == 10 ** length: return str(int_n + 2)
pre = int(n[:(length+1)//2]) # 获取n的前半部分
# 构造三个候选回文数
tmp = [s[:length//2] + s[::-1] for s in [str(pre + dx) for dx in (-1, 0, 1)]]
# 在候选回文数中找出与n差的绝对值最小的那个
return min(tmp, key=lambda x: (x==n, abs(int(x)-int_n)))
Explore
对于小于10的数（1到9），每个数本身就是回文数，所以其最近的回文数是其自身或者相邻的整数。由于题目可能要求找到与原数不同的回文数，返回n-1提供了一个最接近且不同于原数的回文数。对于10的幂次方（如10, 100, 1000等），它们的最近回文数一定会在它们的前一个整数，因为下一个可能的回文数相对较远（例如对于10来说，下一个回文数是11）。因此，对于这类数字，返回n-1是找到最接近的回文数的有效方法。
在构造回文数的过程中，通过对前半部分的数字进行减1、不变、加1操作，可以生成三个候选回文数，从而覆盖所有可能接近原数的回文数的情况。例如，如果原数已经是回文数，那么不变的操作可能会生成原始数本身；而加1和减1的操作则分别提供了略大于和略小于原数的回文数，从而可以确保在不同情况下找到最接近的回文数。
在构造回文数时，奇数长度和偶数长度的数字处理稍有不同。对于奇数长度的数字，其中间的数字应包含在前半部分，这是因为回文数的中心点对称。例如，对于数字12321，前半部分是123。而对于偶数长度的数字，前半部分直接截取到中间即可，例如对于数字1221，前半部分是12。这样的处理确保了构造出的回文数保持对称性，无论原数字的长度是奇数还是偶数。
在题解中，min函数使用了一个lambda表达式来确定最优的回文数。这个lambda表达式设定了两个排序准则：首先比较生成的回文数是否与原数相等（x==n），然后比较它们与原数的绝对差值（abs(int(x)-int_n)）。这种方式首先排除了与原数相同的数，然后在剩下的候选中选择差值最小的。如果有多个候选的差值相等，min函数默认返回第一个遇到的最小数值，这样就同时考虑了差值最小和数值大小，确保找到最接近且有效的回文数。