This is my second article about getting started

1. Title Description

9. A palindrome

Given an integer x, return true if x is a palindrome integer; Otherwise, return false.

Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Second, train of thought analysis

  • Palindrome numbers are symmetrical. The conventional solution is to simply reverse the number and compare it to the original number. Reversing numbers is also easy to implement in Java.
  • To do the inversion, you first convert a number to a string. The results are obtained using Java’s native inversion.
public boolean isPalindrome(int x) {
    String str = String.valueOf(x);
    return new StringBuilder(str).reverse().toString().equals(str);
}
Copy the code

  • This kind of comparison opportunism, below we come to realize palindrome number determination through algorithm analysis!
  • First of all, we can make decisions for special cases so that we can make decisions quickly and make the program more efficient. For example, the palindrome requirement is satisfied for the units digit.
  • Second, it’s not palindrome for negative numbers, because a negative number only appears in the front of the number and nowhere else.
  • Anything with zero in its units digit is not a palindrome number, because if you have zero in each digit then the first digit has to be zero, and we know that natural numbers don’t start with zero.
  • The following is an analysis picture taken from the leetcode website. We can also see from the picture that we need to treat parity differently!

  • We don’t have to go all the way to the end, the inverted number starts at 0, starts smaller than the source number, and knowing that the inverted number is greater than or equal to the source number means we don’t need to reverse.
public boolean isPalindrome2(int x) {
    if (x < 0 || (x % 10= =0&& x ! =0)) {
        return false;
    }
    int result = 0;
    while (result < x) {
        result = result * 10 + x % 10;
        x /= 10;
    }
    return x == result || x == result / 10;
}
Copy the code

Third, summary

  • Palindromes are one of leetcode’s simplest and often used in interviews. We mainly examine our understanding of the time space complexity of the algorithm.