The title comes from LeetCode problem No. 9: palindromes. The difficulty of the questions is Easy and the current pass rate is 56.0%.

Topic describes

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:true
Copy the code

Example 2:

Input: -121 Output:falseInterpretation: Read from left to right as -121. Read from right to left, 121-. So it's not a palindrome number.Copy the code

Example 3:

Input: 10 Output:falseInterpretation: Read from right to left as 01. So it's not a palindrome number.Copy the code

Advanced:

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

title

Solution 1: ordinary solution

One of the best understood solutions is to turn integers into strings and then split the strings into arrays, looping through half the length of the array to see if the corresponding elements are equal.

Animation description

Code implementation

/// Just look at it
class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr); }}Copy the code

Solution two: advanced solution — mathematical solution

The corresponding numbers of integers are obtained by the round and mod operations for comparison.

Take, for example, the number 1221.

  • By calculating 1221 over 1000, we get 1 in the first place
  • By calculating 1221% 10, we get the last digit 1
  • To compare the
  • I’m going to take the 22 out and continue the comparison

Animation description

Code implementation

class Solution {
    public boolean isPalindrome(int x) {
        // boundary judgment
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if(left ! = right)return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true; }}Copy the code

Solution three: advanced solution – ingenious solution

If you look at palindromes intuitively, it’s like folding numbers in half to see if they match.

So the operation of this solution is to take the last part of the number and flip it.

One thing to note here is that since the palindrome number has even and odd bits, when it is even in length, it should be equal in half; When its length is odd, then when folded in half, one of its lengths needs to be removed by one digit (divide by 10 and round).

Specific practices are as follows:

  • For each mod operation (%10), extract the lowest number:y = x % 10
  • Add the lowest number to the end of the number taken out:revertNum = revertNum * 10 + y
  • Every time you pick the lowest number, you divide x by 10
  • judgexStudent: Is it less thanrevertNumWhen it is less than, it indicates that the number is already in half or half
  • Finally, the value of revertNum is equal to x if revertNum is even. If it’s odd, the middle number is in the lowest value of the revertNum, and when you divide it by 10 it should be equal to x.

Animation description

Code implementation

class Solution {
    public boolean isPalindrome(int x) {
        // Return false if the end is 0
        if (x < 0 || (x % 10= =0&& x ! =0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10; }}Copy the code

End

Pay tribute to LGD