Java AC Solution with detailed comments.


  • 0

    To be honest, I do not really like this problem. Just a bunch of cases to think about.

    char[] origin;
    int len;
    long num;
    public String nearestPalindromic(String n) {
        if(n==null) return new String();
        len = n.length();
        if(len==0) return new String();
        origin = n.toCharArray();
        char[] digits = n.toCharArray();
        num = Long.parseLong(n);
        long res = 0;
        //if the current number is not a palindrome, make it a palindrome.
        if(!isPalindrome(digits)){
            makePalindrome(digits);
        }
        //if the current number is not the same to the original number, initialize result with its value.
        long current = getLong(digits);
        if(current!=num){
            res = current;
        }
        
        //check if the length of n is odd or even.
        if(len%2==0){
            if(digits[len/2]>'0'){
                digits[len/2] = (char)(digits[len/2] - 1);
                digits[len/2 - 1] = digits[len/2];
                long temp1 = getLong(digits);
                long temp2 = 0;
                if(digits[len/2]<'8'){ //<'8' since I did digits[len/2] - 1 above.
                    digits[len/2] = (char)(digits[len/2] + 2);
                    digits[len/2 - 1] = digits[len/2];
                    temp2 = getLong(digits);
                    if(Math.abs(num - temp1) <= Math.abs(res - num)) res = temp1;
                    if(Math.abs(num - res) > Math.abs(temp2-num)) res = temp2; 
                }
                else{//for conditions like "1991", should change it to "1881".  
                    if(Math.abs(num - temp1) <= Math.abs(res - num)) res = temp1;
                }
            }
            else{//for conditions like "1001", you cannot do '0'-1 here, '0' can only be '1' here.
                digits[len/2] = '1';
                digits[len/2 - 1] = '1';
                long temp = getLong(digits);
                if(Math.abs(num - temp) < Math.abs(res - num)) res = temp;
            }
        }
        else{//process here is almost the same, just for odd length condition
            if(digits[len/2]>'0'){
                digits[len/2] = (char)(digits[len/2] - 1);
                long temp1 = getLong(digits);
                long temp2 = 0;
                if(digits[len/2]<'8'){
                    digits[len/2] = (char)(digits[len/2] + 2);
                    temp2 = getLong(digits);
                    if(Math.abs(num - temp1) <= Math.abs(res - num)) res = temp1;
                    if(Math.abs(num - res) > Math.abs(temp2-num)) res = temp2; 
                }
                else{
                    if(Math.abs(num - temp1) <= Math.abs(res - num)) res = temp1;
                }
            }
            else{
                digits[len/2] = '1';
                long temp = getLong(digits);
                if(Math.abs(num - temp) < Math.abs(res - num)) res = temp;
            }
        }
        //after having done all the stuff above, another 2 conditions still need to be checked.
        //for example, the answer to "11" should be "9", not "00" or "0". And the answer to "99" should be "101" not "88".
        //So for the next step, I generate numbers having 1 less length and filled with 9, and another number having 1 more length with starting and ending 1, and the rest digits are 0s.
         if(len>1){
            long temp1 = 0;
            for(int i = 0; i<len-1;i++){
                temp1 = temp1*10 + 9;
            }
            long temp2 = 1;
            for(int i = 0; i<len; i++){
                temp2 *= 10;
            }
            temp2 += 1;
            if(Math.abs(res-num)>=Math.abs(num - temp1)){
                res = temp1;
            }
            
            if(Math.abs(res-num)>Math.abs(temp2 - num)){
                res = temp2;
            }
        }
        return "" + res;
        
    }
    
    //make the char array palindrome. Since you want to have the smallest difference, use higher digits to change the lower digits.
    private void makePalindrome(char[] digits){
        int i = 0;
        int j = len - 1;
        while(i<j){
            digits[j] = digits[i];
            i++;
            j--;
        }
    }
    
    //check if the number(char array) is palindrome
    private boolean isPalindrome(char[] digits){
        int i = 0;
        int j = digits.length - 1;
        while(i<j){
            if(digits[i]!=digits[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    //get long value from the char array
    private long getLong(char[] digits){
        long ret = 0;
        for(int i = 0; i< digits.length; i++){
            ret = ret*10 + (digits[i] - '0');
        }
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.