X

LEETCODE 564. Find the Closest Palindrome 解题思路分析

题目大意:

寻找最近的回文数

给定一个整数 n ,你需要找到与它最近的回文数(不包括自身)。

“最近的”定义为两个整数差的绝对值最小。

示例 1:

输入: "123"
输出: "121"

注意:

  1. n 是由字符串表示的正整数,其长度不超过18。
  2. 如果有多个结果,返回最小的那个。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: 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。

这个基本思路其实非常好理解,而本题的难点在于特殊情况太过复杂,我们分别列举一下:

  1. 当数字的左半部分是10的n次幂时(比如10,100,1000,。。。),减一操作后左半部分的位数会少一位,比如数字10002,左半部分为100,按照上面的基本思路,我们需要分别用100,101和99构建镜像回文,问题出在99上,上文我们说过,当原数字长度为奇数时,构建回文时a部分的最后一位不要做镜像处理,但99的最后一位不做处理的话,组成的回文数字会是999,而我们想要的结果显然应该是9999。因此当减一操作后数字的位数与原先的a部分相比减少了一位的话,那么该部分在进行构建回文操作时,最后一位也需要做镜像处理。
  2. 当原数字n为1位数时,返回n-1。比如7,返回6
  3. 当原数字n每一位都是9时,返回n+2。比如999,返回1001
  4. 当原数字n是10的n次方时,返回n-1。比如10000,返回9999
  5. 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-解题思路分析/
Categories: leetcode
kwantong: