题目大意：
寻找最近的回文数
给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: "123" 输出: "121"
注意:
- n 是由字符串表示的正整数，其长度不超过18。
- 如果有多个结果，返回最小的那个。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=564
解题思路分析：
这道题的特殊情况比较多，解决起来实在头疼。个人感觉这类题目不应该出现在白板面试中，至少我作为面试官绝对不会提出这类问题。
言归正传，首先我们考虑下核心思想，首先把数字从中间分成a、b两部分，如果长度是奇数就给a多分点。比如将1234分为12和34，再比如12345可分为123和45。然后用a、a+1、a-1分别构建一个回文数，以1234为例，我们使用12 (a部分)，13 (a部分加一)，11 (a部分减一)分别构建三个回文是1221，1331和1111。此时选择一个距离原数字1234最近的一个即可。另外注意数字长度为奇数时，构建回文时a部分的最后一位不要做镜像处理（但有特例，参照下文）。比如12345的左半部分为123，我们使用123，122和124构建出的回文分别是12321（注意不是123321），12221和12421。
这个基本思路其实非常好理解，而本题的难点在于特殊情况太过复杂，我们分别列举一下：
- 当数字的左半部分是10的n次幂时（比如10，100，1000，。。。），减一操作后左半部分的位数会少一位，比如数字10002，左半部分为100，按照上面的基本思路，我们需要分别用100，101和99构建镜像回文，问题出在99上，上文我们说过，当原数字长度为奇数时，构建回文时a部分的最后一位不要做镜像处理，但99的最后一位不做处理的话，组成的回文数字会是999，而我们想要的结果显然应该是9999。因此当减一操作后数字的位数与原先的a部分相比减少了一位的话，那么该部分在进行构建回文操作时，最后一位也需要做镜像处理。
- 当原数字n为1位数时，返回n-1。比如7，返回6
- 当原数字n每一位都是9时，返回n+2。比如999，返回1001
- 当原数字n是10的n次方时，返回n-1。比如10000，返回9999
- n等于11时，返回9。
实现代码：（本题代码写的稍微有些乱，如果你已理解上面的思路，建议自行编写。以下代码仅供参考）
public String nearestPalindromic(String n) {
long num=Long.valueOf(n); // 数字长度
boolean isOdd=n.length()%2==1; // 长度是否为奇数
if(num<10) return String.valueOf(num-1); // 特例：数字小于10，返回n-1
// 特例：每一位都是9，返回n+2
if(isAllNine(n)) return String.valueOf(num+2);
// 特例：是10的n次方，返回n-1
boolean isTenTimes=isAllNine(String.valueOf(num-1));
if(isTenTimes) return String.valueOf(num-1);
// 特例：如果是11，返回9
if(num==11) return String.valueOf(9);
// 取得数字的前半部分
String half=n.substring(0,isOdd?n.length()/2+1:n.length()/2);
// 利用前半部分组成回文
String res1Str=getPalindromic(half, isOdd);
long res1=Long.valueOf(res1Str); // long型回文
long diff1=Math.abs(num-res1); // 与原数字的绝对值差
long halfLong=Long.valueOf(half);
String res2Str;
// 利用前半部分减一后的数字组成回文
// 如果减一操作后位数减少
if(half.length()!=String.valueOf(halfLong-1).length()){
// 按照原数字长度为偶数位处理
res2Str=getPalindromic(String.valueOf(halfLong-1), false);
}else{
res2Str=getPalindromic(String.valueOf(halfLong-1), isOdd);
}
long res2=Long.valueOf(res2Str);
long diff2=Math.abs(num-res2);
// 利用前半部分加一后的数字组成回文
String res3Str=getPalindromic(String.valueOf(halfLong+1), isOdd);
long res3=Long.valueOf(res3Str);
long diff3=Math.abs(num-res3);
// 如果res1等于原数字，那么在res2Str和res3Str中选择一个距离原数字更近的
if(res1==num) return diff2<=diff3?res2Str:res3Str;
// 取得三个回文距离原数字的最小距离
long min=Math.min(diff1, Math.min(diff2,diff3));
if(min==diff2) return res2Str;
if(min==diff1) return res1Str;
if(min==diff3) return res3Str;
return null;
}
// 根据前半部分获取回文
String getPalindromic(String s, boolean isOdd){
// 如果原数字位数为奇数，那么前半部分的最后一位不做镜像处理
int length=isOdd?(s.length()*2-1):(s.length()*2);
char[] arr = new char[length];
for(int i=0;i<s.length();i++){
arr[i]=s.charAt(i);
arr[length-i-1]=s.charAt(i);
}
return String.valueOf(arr);
}
// 判断是否每一位都是9
boolean isAllNine(String n){
boolean isAllNine=true;
for(int i=0;i<n.length();i++){
if(n.charAt(i)!='9'){
return false;
}
}
return isAllNine;
} 本题解法执行时间为2ms。
Runtime: 2 ms, faster than 92.21% of Java online submissions for Find the Closest Palindrome.
Memory Usage: 39.8 MB, less than 14.06% of Java online submissions for Find the Closest Palindrome.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-564-find-the-closest-palindrome-解题思路分析/