JAVA easy understanding comparison solution(18ms) with comments


  • 0

    How is it work

    In my solution, there are 5 situations:

    1. 0
    2. 11
    3. single digit like 1~9
    4. 10 based number like 10, 100, 1000 etc.
    5. the others

    The most complicated one is situation 5, cause there would be 3 close palindromes of 1 number:

    1. palindrome by itself
    2. palindrome a little bigger than itself
    3. palindrome a little smaller than itself

    So, the value offset is to generate them. Then, we get palindrome with the offset number. And finally, we compare three of them, and get the closest and smaller one.

    Complexity

    The time O is 3 * n/2 + 3= n

    Code

    public String nearestPalindromic(String n) {
    	long num = Long.valueOf(n);
    	if (num == 0) return "1";
    	if (num == 11) return "9";
    	if (num <= 10 || Math.log10(num)%1==0) return num - 1 + "";
    	
    	long exp = n.length() - (n.length() - 1) / 2 - 1;
    	long offset = (long) Math.pow(10, exp);
    	
    	return min(num, palindry(n), palindry(num + offset + ""), palindry(num - offset + ""));
    }
    
    //choose the closest number away from target
    private String min(long target, long s1, long s2, long s3) {
    	long[] array = { s1, s2, s3 };
    	long[] distance = new long[3];
    	for (int i = 0; i < array.length; i++) {
    		distance[i] = Math.abs(target - array[i]);
                    //exclude itself
    		if (distance[i] == 0) distance[i] = Long.MAX_VALUE;
    	}
    
    	int minIndex = distance[0] > distance[1] ? 1 : 0;
    	return array[distance[2] > distance[minIndex] ? minIndex : 2] + "";
    }
    
    //get a normal palindrome number
    private long palindry(String n) {
    	char[] c = n.toCharArray();
    	for (int i = 0; i < c.length / 2; i++) {
    		c[c.length - i - 1] = c[i];
    	}
    	return new Long(new String(c));
    }
    

Log in to reply
 

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