0564 寻找最近的回文数候选枚举从暴力到常数的推导指南【免费下载链接】AAWirelessDongleUse Wireless Android Auto with a car that supports only wired Android Auto using a Raspberry Pi.项目地址: https://gitcode.com/GitHub_Trending/aa/AAWirelessDongle给定一个长度最多 18 位的整数串要求找出与它最近、且不是它自身的回文数。核心思路是把无限的候选空间压成常数个对前缀做 ±1 再镜像外加两个位数边界兜底。读完这篇你带走的是「构造最近 X」类题型的候选集框架而不只是这一题的答案。一、读题从题目里提取 3 个信号先别急着写代码。题面藏着三个信号每个都指向一个设计决策。信号题目给出的信息它提醒我们什么输入形式整数用字符串n给出不含前导 0长度可达 18 位直接当整数算容易溢出切片、拼接、反转更稳数值范围1 ≤ n.length ≤ 18取值[1, 10^18-1]回文数数量巨大暴力遍历必超时候选必须压到常数规模平局规则多个同样近的结果返回较小的那个比较键不能只看差值还得再比一次数值大小三个信号里第三个最容易被漏。它直接决定了最后取min时那个 key 该怎么构造。二、推理路径候选集怎么被压到常数为什么暴力走不通。在10^18的量级里回文数动辄上百亿个。就算逐个生成、逐个比差值时间上也算不完。这条路直接判死刑。候选集如何压缩。关键观察一个回文数完全由它的前半部分决定后半部分只是前半的镜像。所以离n最近的那个回文它的前半部分必然贴着n的前半部分最多只相差 1。候选由此被压成常数几个全 9比n少一位当下边界100…001比n多一位、首尾为 1当上边界前缀原样不动直接镜像前缀 1再镜像前缀 −1再镜像。完备性一句话论证。若某个回文的前半部分与n的前半相差超过 1就一定能构造出更贴近n的回文矛盾。因此只需盯着 ±1 这三个方向即可。位数边界由谁兜底。当「前缀 ±1」触发位数坍缩时例如1000的前缀减 1 后由10变9镜像结果的位数会缩水此时真正的答案落在两个边界候选里——全 9 从下界兜底100…001从上界兜底。三、实现完整可运行代码class Solution: def nearestPalindromic(self, n: str) - str: length len(n) cands set() # 下边界比 n 少一位的全 9 cands.add(str(10 ** (length - 1) - 1)) # 上边界比 n 多一位、首尾为 1 cands.add(str(10 ** length 1)) # 前缀长度偶数取一半奇数多含中间位 half (length 1) // 2 prefix int(n[:half]) for delta in (-1, 0, 1): head str(prefix delta) if length % 2 0: # 偶数位前缀整体反转当尾 pal head head[::-1] else: # 奇数位去掉中间位再反转 pal head head[-2::-1] cands.add(pal) # n 本身是回文时必须剔除 cands.discard(n) target int(n) # (差值, 数值) 二元组差值相同取较小值 return min(cands, keylambda s: (abs(int(s) - target), int(s)))关键行速览half (length 1) // 2前缀长度公式偶数恰好一半奇数多含中间位偶数分支head head[::-1]奇数分支head head[-2::-1]镜像拼接的两个分支head[-2::-1]的意思是从倒数第 2 位取到开头并反转等价于「去掉中间位再整体反转」返回行的key是(abs(int(s) - target), int(s))平局取小的落点。四、自检边界用例与易漏坑四个必须过的用例每类边界各占一个用来验证上面的推导没有漏输入关键候选答案考察点10、2、110一位数0与2差值同为 1取小109、11、22、1019形如 10前缀 −1 坍缩成09988、101、1001101全 9n本身被剔除1000999、1001、1111、10001999形如 1000下边界全 9 兜底三条易漏坑必须剔除自身。n是回文时delta0的镜像恰好等于n不剔除就会被选成差值 0。用discard而非remove即使不在集合里也不报错冗余候选无害。前缀 ±1 位数变化时会冒出00、9这类短候选差值过大或互相重复都会被min自然过滤不必额外特判大数溢出。n最长 18 位。Python 的int无溢出直接算即可移植到 C/Java 时优先用字符串做镜像只对前缀 ±1 做小整数运算。五、复杂度时间O(L)。候选只有常数个每个候选的生成与比较都是O(L)的字符串操作。空间O(1)不计输出只存放常数个候选串。运算量不随数值规模增长的原因输入从 1 位到 18 位算法做的永远是「生成 5 个左右候选再比一次」与数值本身的大小无关。六、题图同系列的回文题本题属于回文系列里「构造回文」的一环可以和下面几道对照着读回文数判断回文「反转一半即停」是本课题前缀思想的前身验证回文串双指针逼近从「判断」视角理解回文结构最长回文子串DP 求区间回文与本题「构造回文」互补回文链表把回文判断搬到链表练结构迁移。完整题目索引见 docs/solutions/0500-0599/index.md。这道题真正的收获不在答案本身而在两个可以带走的自问遇到「构造最近 X」候选空间能否被压到常数规模压完之后位数边界处是否还缺兜底候选把这两句问清楚就从暴力走到了最优解。【免费下载链接】AAWirelessDongleUse Wireless Android Auto with a car that supports only wired Android Auto using a Raspberry Pi.项目地址: https://gitcode.com/GitHub_Trending/aa/AAWirelessDongle创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考