纳米AI LeetCode 564.寻找最近的回文数 public String nearestPalindromic(String n)

这是 LeetCode 第 564 题《寻找最近的回文数》，核心是找到与给定字符串n数值最接近的回文数，若存在距离相同的情况则返回较小的那个。以下是完整的分析和高效解决方案：

一、问题核心规则

1. 回文数定义：正读和反读完全相同的数（如121、1331）
2. 若存在两个回文数与n距离相同，返回数值更小的那个
3. 输入n是长度为 1~18 位的字符串，需处理大数避免整数溢出

二、关键思路分析

直接遍历所有可能的数寻找最近回文数效率极低（尤其对于18位大数），最优解法是生成所有候选回文数，然后在候选集中筛选最优解：

候选回文数的生成规则

我们只需要生成5个关键候选即可覆盖所有可能的最优解：

1. 比n位数少1的最大回文数：如n=1000，候选为999
2. 比n位数多1的最小回文数：如n=999，候选为1001
3. 用n的前半部分生成的回文数：如n=12345，前半部分是123，生成12321；n=1234，前半部分是12，生成1221
4. 用n的前半部分+1生成的回文数：如n=12345，生成12421；n=199，生成202
5. 用n的前半部分-1生成的回文数：如n=12345，生成12221；n=100，生成99

三、完整可运行代码

classSolution{publicStringnearestPalindromic(Stringn){longnum=Long.parseLong(n);intlen=n.length();// 生成所有候选回文数Set<Long>candidates=newHashSet<>();// 1. 位数少1的最大回文数（如1000→999）candidates.add((long)Math.pow(10,len-1)-1);// 2. 位数多1的最小回文数（如999→1001）candidates.add((long)Math.pow(10,len)+1);// 3. 用前半部分生成基础回文数longprefix=Long.parseLong(n.substring(0,(len+1)/2));for(longi=prefix-1;i<=prefix+1;i++){longcandidate=generatePalindrome(i,len%2==0);candidates.add(candidate);}// 移除自身（如果n本身是回文数）candidates.remove(num);// 寻找最优解longclosest=-1;for(longcand:candidates){if(closest==-1){closest=cand;}else{longdiffCand=Math.abs(cand-num);longdiffClosest=Math.abs(closest-num);if(diffCand<diffClosest){closest=cand;}elseif(diffCand==diffClosest){// 距离相同选较小的closest=Math.min(closest,cand);}}}returnString.valueOf(closest);}// 根据前缀生成回文数privatelonggeneratePalindrome(longprefix,booleanisEven){longpalindrome=prefix;// 偶数长度：直接反转前缀拼接；奇数长度：反转前缀去掉最后一位if(!isEven){prefix/=10;}while(prefix>0){palindrome=palindrome*10+prefix%10;prefix/=10;}returnpalindrome;}}

四、关键细节解释

1. 大数处理

安全警告：
输入n最大为18位，超过Integer.MAX_VALUE（约2e9），必须用long类型存储，避免溢出

2. 候选生成逻辑

3. 最优解筛选

• 先比较与原数的绝对值差，差小的优先
• 若差相等，选择数值更小的回文数

五、边界测试用例

// 测试用例1：n本身是回文数System.out.println(newSolution().nearestPalindromic("121"));// 输出111（或131，距离相同选小的）// 测试用例2：n是10的幂System.out.println(newSolution().nearestPalindromic("1000"));// 输出999// 测试用例3：n是999System.out.println(newSolution().nearestPalindromic("999"));// 输出1001// 测试用例4：n是18位大数System.out.println(newSolution().nearestPalindromic("999999999999999999"));// 输出1000000000000000001

六、下一步建议

1. 可以尝试手动模拟generatePalindrome方法的执行过程，理解回文数生成逻辑
2. 思考如何处理输入为"1"这种极端短字符串的情况（候选为0和11，最终返回0）
   以上内容由AI搜集并生成，仅供参考