564. Find the Closest Palindrome

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1].

Solution:

class Solution {
    public String nearestPalindromic(String n) { // n = "12345"
        int len = n.length(); // 5
        int i = 0; 
        if (len % 2 == 0){ // even    5 % 2 ! =0
            i = len/2 -1;  
        }else {        
            i = len/2;         // i = 2
        }

        long firstHalf = Long.parseLong(n.substring(0, i + 1));
        // n.substring(0, 2 + 1) = n.substring(0, 3)
        // 12 3 

        /*

        Generate possible palindromic candidates:
        1. Create a palindrome by mirroring the first half
        2. Create a palindrome by mirroring the first half incremented by 1.
        3. Create a palindrome by mirroing the first half decremented by 1.
        4. Handle edge case by considering palindromes of the form 999...
        and 100....001(smallest and largest n - digit palindromes).

        */
        List<Long> possibilities = new ArrayList<>();

        possibilities.add(halfToPalindrome(firstHalf, len % 2 == 0)); // 123, F 
        possibilities.add(halfToPalindrome(firstHalf + 1, len % 2 == 0)); // 124, F
        possibilities.add(halfToPalindrome(firstHalf - 1, len % 2 == 0)); // 122, F
        possibilities.add((long) Math.pow(10, len - 1) - 1); // Math.pow(10, 5-1 ) - 1 = 10^4 - 1 = 9999
        possibilities.add((long) Math.pow(10, len) + 1);// Math.pow(10, 5) + 1 =10^5 + 1= 100000+1=100001

        // Find the palindrome with minimum difference, and minimum value.
        long diff = Long.MAX_VALUE;
        long res = 0;
        long nl = Long.parseLong(n);// 12345
        for (long cand : possibilities){ // 
            if (cand == nl){
                continue;
            }

            if (Math.abs(cand - nl) < diff){
                diff = Math.abs(cand - nl);
                res = cand;
            }else if (Math.abs(cand - nl) == diff){
                res = Math.min(res, cand);
            }
        }

        return String.valueOf(res);

    }

    private long halfToPalindrome(long left, boolean even){ // 123, F
        // Convert the given half to palindrome.
        long res = left; // 123
        if (!even){ // F
            left = left / 10; // 123/ 10 = 12
        }

        while(left > 0){ // 123>0
            res = res * 10 + (left % 10); // 123 * 10 + 12 %10 = 1230 + 2 1232// 1232 * 10 + (2%2 ) =12321
            left = left / 10;      //  12 / 10 =1;  // 0
        }

      //  好一个人类, 这是咋想出来的, 感觉在玩数字...

        return res;
        // 12321
    }
}


// TC: O(n)
// SC: O(n)

class Solution {
    public String nearestPalindromic(String n) {

        if (n.length() == 1){
            String result = Character.toString(n.charAt(0) - 1);
            return result;
        }

        int left = 0;
        int right = n.length() - 1;

        /*
        012
        121
        l r

        0 2

        */


        char[] nArray = n.toCharArray();

        while(left < right - 1){//0<2-1
            if (nArray[left] == nArray[right]){
                left++;
                right--;
            }else{
                nArray[right] = nArray[left];
                left++;
                right--;
            }
        }

        // 12 3 4 
        // l    r
        //  l r
        //  

        // 3 3 3
        //    

        if (left == right){
            // if (n.charAt(right + 1) > nArray[right + 1]){
                return new String(nArray);
            //}
        }else{
            // if (n.charAt(left) < n.charAt(right)){
            //     nArray[right] = n.charAt(left); 
            // }else{
            //     nArray[left] = n.charAt(right);
            // }
            nArray[right] = n.charAt(left); 

            return new String(nArray);
        }
    /*    1 2 3 1 
          l 
                r
            l r    
        */




        /*
              123

        >1       2    1 <
        */
    }
}

// 处理边界值卡了

?/?