LeetCode's Journey Tour [Simple]-9. Palindrome

Posted May 27, 20203 min read

Title
================================================== =======

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:
Input:121
Output:true

Example 2:
Input:-121
Output:false
Explanation:From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input:10
Output:false
Explanation:Reads 01 from right to left. Therefore it is not a palindrome.

Personal ideas

Option 1:Convert to string

First, convert the number into a string; then make a judgment, using a loop, each time take the string i position character and length-1-i position character for comparison(length is the length of the string) If it is different, it returns false.
Next, consider the value of i, from 0 to length/2(not included), if length is an odd number, and if the given number is a palindrome, then i is just after jumping out of the loop Is the middle position of the string, no matter what the position is, this number is a palindrome; if length is an even number, then the final value of i in the loop is length/2-1, because The string count starts from 0. At this time, i and length-1-i are just the two middle positions of the string, as long as they are compared. Through the above analysis, we can see that we do not need special treatment.
In addition, as can be seen from the given example, negative numbers are not palindromes.
Here is the code:

class Solution {
    public boolean isPalindrome(int x) {
        if(x <0) {
            return false;
        }
        String str = String.valueOf(x);
        int len   = str.length();
        for(int i = 0; i <len/2; i ++) {
            if(str.charAt(i)! = str.charAt(len-1-i)) {
                return false;
            }
        }
        return true;
    }
}

The execution result is:

Execution time:10 ms, defeating 69.46%of users in all Java submissions
Memory consumption:38.9 MB, defeating 5.14%of users in all Java submissions

Option 2:flip the data

There is an advanced question in the title:

Could you solve it without converting the integer to a string?

The number of palindromes is equal to the original number after flipping. We can flip the given data. If the flipped number exceeds the limit or is not equal to the original number, it is not a palindrome. Then we can use integer inversion the results here:

class Solution {
    public boolean isPalindrome(int x) {
        if(x <0) {
            return false;
        }
        if(reverse(x) == x) {
            return true;
        } else {
            return false;
        }
    }

    public static int reverse(int x) {
        int result = 0;
        while(x! = 0) {
            if(x> 0 && result>(Integer.MAX_VALUE-x%10)/10)
                return 0;
            result = result * 10 + x%10;
            x = x/10;
        }
        return result;
    }
}

The execution result is:

Execution time:10 ms, defeating 69.46%of users in all Java submissions
Memory consumption:39 MB, defeating 5.14%of users in all Java submissions

Other thinking

Option 3:flip half

After looking at the ideas in the discussion area, the official said that we can flip the number by half. What is particularly annoying here is the special treatment of multiples of 10

class Solution {
    public boolean isPalindrome(int x) {
        if(x <0) {
            return false;
        }
        if(x%10 == 0 && x> 0)
            return false;
        int xr = 0;
        while(x> xr) {
            xr = xr * 10 + x%10;
            x = x/10;
        }
        return xr == x || xr/10 == x;

    }
}

The execution result is:

Execution time:9 ms, defeating 99.22%of users in all Java submissions
Memory consumption:39.1 MB, which beat 5.14%of users in all Java submissions