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 integersX
Are positive order and reverse order the same, then integersx
Convert 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 take
x
The lowestt
, i.e.,t = x%10
- Assigned to
reversX
, 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 😁