题目

Palindrome Number

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-231 <= x <= 231 - 1

Follow up: Could you solve it without converting the integer to a string?

解法

方法一：字符串反转

public class PalindromeNumber9 {
          
   

    public static void main(String[] args) {
          
   
        int a = 121;
        boolean palindrome = Solution.isPalindrome(a);
        System.out.println(palindrome);

    }

    /**
     * 反转字符串
     *
     * @author aiwenwen
     * @date 11:08 2022/6/10
     **/
    static class Solution {
          
   
        static public boolean isPalindrome(int x) {
          
   
            String revBefore = String.valueOf(x);

            StringBuffer strUtil = new StringBuffer();
            strUtil.append(revBefore);
            String revAfter = strUtil.reverse().toString();

            if (revBefore.equals(revAfter)) {
          
   
                return true;
            }

            return false;
        }
    }
}

方法二：反转一半数字

/**
     * 反转一半数字
     *
     * @author aiwenwen
     * @date 11:08 2022/6/10
     **/
    static class Solution2 {
          
   
        static public boolean isPalindrome(int x) {
          
   
            /**
             *特殊情况：
             * 如上所述，当x<0时，x不是回文数。
             * 同样地，如果数字的最后一位是0，为了使该数字为回文，
             * 则其第一位数字也应该是0
             * 只有0满足这一属性
             **/
            if (x < 0 || (x % 10 == 0 && x != 0)) {
          
   
                return false;
            }

            int revertedNumber = 0;
            while (x > revertedNumber) {
          
   
                revertedNumber = revertedNumber * 10 + x % 10;
                x /= 10;
            }

            /**
             *
             *当数字长度为奇数时，我们可以通过revertedNumber / 10去除处于中位的数字。
             * 例如，当输入为 12321 时，在while循环的末尾我们可以得到 x = 12, revertedNumber = 123,
             * 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
             **/
            boolean b = x == revertedNumber;
            boolean b1 = x == revertedNumber / 10;

            return b || b1;

        }
    }

复杂度分析

时间复杂度：O(logn)，对于每次迭代，我们会将输入除以 10，因此时间复杂度为 O(logn)。 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

转载