This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

preface

The palindrome number of question 9 is as follows:

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.

 

Example 1:

Input: x = 121 Output: true

Example 2:

Input: x = -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.

Example 3:

Input: x = 10 Output: false Description: Read from right to left, 01. So it’s not a palindrome number.

Example 4:

Input: x = -101 Output: false

A, thinking

This topic is short and easy to understand, so I will directly talk about the idea.

You want to judge integersXAre positive order and reverse order the same, then integersxConvert to stringstr. And then you take the stringstr, compared to its inverted string.

Practical examples:

Here, the integer 12345321 is used as an example to compare the original string with the reversed string

  • If all are the same: palindrome number
  • There are different numbers: not palindromic numbers

After the above analysis, the idea is a total of three steps: 1. Integer to string 2. Compare the two strings in turnCopy the code

Second, the implementation

Thought had realized rise also is not what difficult thing.

The implementation code

    public boolean isPalindrome(int x) {
        // The original string
        String str = String.valueOf(x);
        // Invert the string
        String reverseStr = new StringBuilder(str).reverse().toString();
        // Compare in sequence
        for (int i=0; i<str.length(); i++) {
            // Return false as long as it is not equal
            if(! (str.charAt(i) == reverseStr.charAt(i)))return false;
        }
        return true;
    }
Copy the code

The execution result

Three, how to improve

Optimization Scheme 1

A fierce operation such as tiger, beat 20% at a glance. What went wrong with the above code? In fact, it’s not hard to see that at some point the above inversion of strings is useless. For example, if 1234567887654321 is an integer, compare characters 16 times. In order to reduce the number of comparisons as much as possible, the optimization is carried out from the following two aspects

  • Just compare the first half of the string
  • Exclude positive numbers with negative and units digits 0 (obviously neither negative nor positive numbers with units digits 0 are palindromes)

The implementation code

    public boolean isPalindrome(int x) {
        // The negative number or the ones bit is 0
        if (x < 0 || (x%10= =0&& x ! =0)) {
            return false;
        }
        // The original string
        String str = String.valueOf(x);
        // Invert the string
        String reverseStr = new StringBuilder(str).reverse().toString();
        // Compare in sequence (only half)
        for (int i=0; i<str.length()/2; i++) {
            // Return false as long as it is not equal
            if(! (str.charAt(i) == reverseStr.charAt(i)))return false;
        }
        return true;
    }
Copy the code

The execution result

Obviously, the effect of plan one is not obvious

Optimization Plan 2

Not hard to see, the inversion string in plan 1 still takes a lot of time. For efficiency, strings can no longer be used for comparison. So how do you do that? It’s easy to compare the first half of an integer X with the reverse of the second half of X. If the first half of 123321 is 123 and the second half is 321, it is obvious that 123321 is a palindrome.

A clever inversion

X: A primitive integer reversX: an integer that is reversed

The specific operation is divided into the following two steps:

  • Every time I takexThe lowestt, i.e.,t = x%10
  • Assigned toreversX, i.e.,reversX = reversX * 10 + t(A low position in X is a high position in reversX)

Code implementation

Considering the length of integers (even and odd)

  • Length is even: x == reverseX
  • ReverseX == reverseX / 10
    public boolean isPalindrome(int x) {
        // The negative number or the ones bit is 0
        if (x < 0 || (x % 10= =0&& x ! =0)) {
            return false;
        }

        int reverseX = 0;
        while (x > reverseX) {
            // The lowest integer value
            int t = x % 10;
            // Inverts to the high end of the integer
            reverseX = reverseX * 10 + t;
            // Discard the lowest value
            x /= 10;
        }

        // If the integer length is odd, x == reverseX / 10;
        return x == reverseX || x == reverseX / 10;
    }
Copy the code

The execution result

The improvement is very noticeable!

Four,

Today is the ninth buckle ~ this series will update the buckle 1-10 questions, continuous update for 10 days! Dig gold coin, I come 😁