Java solution using long to store value instead of String.


  • 0

    Similar to other solution, we try to find the minimum distance of left+1, left-1, and left.
    When the values are 100000...00 or 10000...001, the answers are always 999999..999.
    On the other hand, when the values are 999...999, the answers are always 10000...001.
    Therefore, using long value is easier to check these two types of patterns.
    First, the value is split into two parts from the middle, left and right.
    If reverse(left)==1 and right<=1 , then these patterns are 100000...00 or 10000...001.
    If left+1==10^n and right+==10^n , then these patterns are 999...999.
    In addition, we can calculate the distances using the long value instead of parsing the strings.

    public class Solution {
        String long2String(long num, int len) {
            StringBuilder sb = new StringBuilder();
            while ( num > 0 || len > 0) {
                sb.append(num%10);
                num/=10;
                len--;
            }
            return sb.reverse().toString();
        }
        long reverseLong(long num) {
            long ret = 0;
            while ( num > 0) {
                ret = (ret * 10) + ( num % 10 );
                num/=10;
            }
            return ret;
        }
        public String nearestPalindromic(String n) {
            if (n==null || n.length()==0 ) return "";
            int len = n.length();
            if (len==1) return ""+ ((n.charAt(0)-'0')-1);
            int odd = len%2;
            String left = n.substring(0, len/2+odd);
            String right = n.substring(len/2+odd);
            long leftValue = Long.parseLong(left), rightValue = Long.parseLong(right);
            long revLeftValue = reverseLong(leftValue/(long)Math.pow(10l,odd) );
            if (reverseLong(leftValue)==1 && rightValue<=1  ) //100000, 100001
                return ""+( (long) Math.pow(10l,len-1)-1);  
            long tens = (long) Math.pow(10l, right.length());
            if (leftValue+1==tens*((long)Math.pow(10l,odd)) && rightValue+1==tens) //99999
                return ""+( (long) Math.pow(10l,len)+1);
            long dis = Math.abs(rightValue - revLeftValue);
            if (dis==0) dis = Long.MAX_VALUE;
            String ret = left + long2String(revLeftValue, len/2);
            long lowValue = reverseLong((leftValue-1)/(long)Math.pow(10l,odd) );
            long diff = tens + rightValue - lowValue;
            if (diff <= dis ) {
                dis = diff;
                ret = leftValue-1 == 0? "9": ""+ (leftValue-1) +  long2String(lowValue, len/2);
            }
            long highValue = reverseLong((leftValue+1)/(long)Math.pow(10l,odd) );
            diff = tens + highValue - rightValue;
            if (diff < dis ) {
                return ""+ (leftValue+1) + long2String(highValue, len/2);
            }
            return ret; 
        }
    }
    

Log in to reply
 

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