This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

The title is as follows:

Given an integer x, return true if x is a palindrome; Otherwise, return false. Palindromes are integers that are read in the same order (from left to right) and in the same order (from right to left). For example, 121 is a palindrome, while 123 is not.

The first way to determine if a number is palindrome is to convert it into a string and then invert the string to see if it is the same. For example:

If the reversed string is not the same, it is not a palindrome.

Invert after the same number, is the palindrome number. The resulting code is as follows:

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));
    }

    public static boolean isPalindrome(int x) {
        // Convert the number to a string
        String str = String.valueOf(x);
        // Reverse it
        String newStr = new StringBuilder(str).reverse().toString();
        returnstr.equals(newStr); }}Copy the code

Submit to LeetCode:

At the end of the topic, there is an advanced requirement:

Advanced: Can you solve this problem without converting integers to strings?

How do you do this without strings? In fact, it’s very simple. You can directly reverse the number by calculating, for example, 1234. First, we need to get the units digit 4 of the number. The remainder is 10:

Let’s divide 1234 by 10 to get the number 123. Let’s leave 123 remaining by 10 to get 3:

By analogy, each digit in the number can be obtained:

And then we multiply each of these by its carry, so since we’re going to reverse, we’re going to do the reverse, we’re going to think of 4 as the thousands place, 3 as the hundreds place, 2 as the tens place, and 1 as the ones place:

The inverted number is obtained: 4 * 1000 + 3 * 100 + 2 * 10 + 1 = 4321.

The code is as follows:

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(121));
    }

    public static boolean isPalindrome(int x) {
        int num = x;
        int result = 0;
        // Reverse the number
        while (x > 0) {
            result *= 10;
            result += x % 10;   // Find each digit
            x /= 10;            
        }
        returnnum == result; }}Copy the code

However, there is a small bug in this program, which is the boundary problem. When a number is reversed, it is larger than the maximum value of int, then the program will make an error:

At this point, result has become a negative value because it exceeds the maximum value that can be represented by int. It can never be equal to the input value, so the program cannot accurately determine whether the input value is a palindrome.

To solve this problem, we can not reverse all the numbers, but reverse half of them, because the nature of palindromes, we only need to know that half of them are the same, then it must be a palindrome.

We need to discuss two cases. First, the number of odd length, take 12321 as an example:

We get the number inverted by half the length:

When it is compared with the first half of the length, it is found that both numbers are 12, indicating that 12321 is a palindrome.

For an even number, use 1221 as an example:

Still get the number half the length reversed:

Compare this with the number inverted by half the length.

So the key is how do you cut and get the numbers? Let’s put numbers of odd and even length together:

First, let it be left by 10 to get the last digit:

Then divide the original number by 10 to eliminate the last digit:

The remainder is 10 to get the last digit:

Divide by 10 to eliminate the last digit:

At this point, the operation should stop, because the even-length number has already obtained half the length of the number, for the even-length case, directly compare whether the newly generated number is equal to the original number; In the case of odd length, although we get half the length of the number, the length of the original number is 3, so we should get it again:

Thus, the loop terminates when the original number is less than or equal to the new number, and in the odd case, we need to divide the last digit and then compare with the original number, so divide the new number by 10 and then compare.

To sum up, the code is obtained:

public class Solution {

    public static void main(String[] args) {
        System.out.println(isPalindrome(12321));
    }

    public static boolean isPalindrome(int x) {
        // A negative number must not be a palindrome
        if (x < 0 || (x % 10= =0&& x ! =0)) {
            // If the last digit of the number is 0, then the first digit of the number must be 0 if the number is a palindrome
            Return false if the last digit is 0, but the number is not 0
            return false;
        }
        int newNum = 0;
        // Stop the loop when the original number is less than or equal to the newly generated number
        while (x > newNum) {
            newNum *= 10;
            newNum += x % 10;
            x /= 10;
        }
        // Compare the newly generated number with the original number
        return x == newNum || x == newNum / 10; }}Copy the code

Submit to LeetCode: