Handled in the collection

A daily collection of LeetCode articles

Title: Palindrome number

Title source: leetcode-cn.com/problems/pa…

Checks whether an integer is a palindrome. Palindromes are integers that read in positive (left to right) and backward (right to left) order.

Example 1:

Input: 121 Output: trueCopy the code

Example 2:

Input: -121 Output: false Description: Read from left to right. The value is -121. Read from right to left, 121-. So it's not a palindrome number.Copy the code

Example 3:

Input: 10 Output: false Description: Read from right to left. The value is 01. So it's not a palindrome number.Copy the code

Advanced:

Can you solve this problem by not converting integers to strings?

Their thinking

In the example given by the question, it can be seen intuitively that negative numbers are definitely not palindromes due to the negative sign, so the first thing we need to do is to determine whether the input number is negative.

Then, according to the characteristics of numbers, we can also know that the ones digit is 0 integer, certainly not palindrome number, if the ones digit is 0 palindrome number, then the first must also be 0, such a number in addition to 0, the rest obviously can not be a palindrome number.

This gives us our first limit judgment, which returns false for all negative numbers, as well as for all non-zero integers with the ones bit of 0.

Now, I don’t know if you think of the integer inversion in the last article, if you reverse the whole input number and you get the same result as the input number, then this is definitely a palindrome, but in this case, we also need to determine whether the inverted number overflows, which is a little bit tricky.

So what would be a better solution, of course, is to simply reverse the last half of the number and compare it with the first half, and return true if they are the same, false if they are different.

The operation of the number reversal is very simple, the input number X directly cycle modulus is good, and then we can divide the input number in the process of the cycle by 10.

The question is how do we tell if we’ve reached half the number of digits?

This problem can be so consider, if the situation is even number palindrome, X and Y are equal, reverse digits have been to a half, if odd number palindrome is the case, then X < Y, reverse digits to a half, then we have to remove the last of the Y, and X, if equal, So this number is the palindrome number of odd digits.

Write the code

After the above analysis, the code is as simple as it should be:

public boolean isPalindrome(int x) {
    // Do the limiting case first
    if (x < 0 || (x % 10= =0&& x ! =0)) return false;

    int revertedNumber = 0;

    // Loop until the revertedNumber is greater than or equal to x
    while (x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

    return revertedNumber == x || x == revertedNumber / 10;
}
Copy the code

By now, I don’t know if there are any students who would like to ask how to solve the problem without adding the sentence “do not convert integers into strings”.

In Java, without this limitation, the code would not be much simpler: Both StringBuilder and StringBuffer in Java provide the reverse() method directly:

public boolean isPalindrome_1(int x) {
    // Do the limiting case first
    if (x < 0 || (x % 10= =0&& x ! =0)) return false;

    StringBuilder stringBuilder = new StringBuilder(String.valueOf(x));
    return stringBuilder.toString().equals(stringBuilder.reverse().toString());
}
Copy the code

To summarize, if you have an integer inversion problem in the future, the basic idea is to take the modulus of the loop, and then multiply by 10 to add up. Palindrome numbers today can be seen as a slightly special “integer inversion” problem.