LeetCode.009.Palindrome Number 判断整数是否回文数

题目描述

009 Palindrome Number
https://leetcode-cn.com/problems/palindrome-number/
https://leetcode.com/problems/palindrome-number/description/

Determine whether an integer is a palindrome. Do this without extra space.

Example 1:

Input: 121
Output: true

Example 2:

Input: -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: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

---

解题过程

判断整数是否回文数，算法很简单，但要考虑溢出就比较麻烦。
题目要求不得使用额外空间（申请临时变量不算），所以不能转为字符串再判断。
首先要知道的常识是：所有负整数都不是回文数。

求输入值的逆置和原值比较(溢出)

如果先求输入整数的逆置，再和原数比较，会有逆置后溢出的风险，我写了个求逆置后判断的版本，是可以AC的，为什么呢？

• 首先，Integer.MAX_VALUE=2147483647范围内最大的回文数是2147447412，其逆置不会溢出。
• 其次，如果输入值x的逆置reverse溢出，reverse会变成负的，肯定和x不相等。

所以即使不考虑溢出此方法也能AC

// Integer.MAX_VALUE范围内最大的回文数是2147447412，其逆置不会溢出
// 如果x的逆置溢出，reverse会变成负的，肯定和x不相等，所以即使不考虑溢出此方法也能AC
public boolean isPalindrome1(int x) {
    if (x < 0) {
        return false;
    }
    int a = x;
    int reverse = 0;
    while (a != 0) {
        reverse = reverse * 10 + a % 10;
        a = a / 10;
    }
    return reverse == x;
}

求输入值后半段的逆置和前半段比较

题目中提示了求逆置有溢出风险，那有没有更好的方法呢？
我也想了比较前后段，但那得知道 x 的位数，求 x 的位数就得把 x 遍历一遍，感觉太麻烦，其实求 x 的逆置过程中就可以知道是否已经处理了一半。
在求 x 的逆置 reverse 过程中如何知道已经处理了 x 位数的一半呢？答案是当 x 小于 reverse 时就表明已经处理了 x 位数的一半，很简单的数学逻辑，竟然没想到。
但是用这种方法需要注意的是10的倍数得单独处理，因为逆置后末尾的0会被忽略，遇到 x 除去末尾 0 是回文时，比如10, 122100，会出现reverse和x相等的情况，但这时候x并不是回文数。

下面是我根据Solution中的思想写的，**在x除以10前后都和reverse比较一下是为了能同时应对偶数位回文(1221)和奇数位回文(121)**，第一版我写的忘了单独处理10的倍数，错了一次，目前版本已经AC：

//只逆置x的后半段，和前半段比较
public boolean isPalindrome(int x) {
    //10的倍数(除了0)肯定不是回文数，因为逆置后第一位的0会被舍去
    //必须单独处理10的倍数，否则遇到122100这种除0外是回文的会出错
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    int reverse = 0;
    while (reverse <= x) { //当x<reverse时，表明已处理了x的后半段
        reverse = reverse * 10 + x % 10;
        //在x除以10前后都和reverse比较一下是为了能同时应对偶数位回文(1221)和奇数位回文(121)
        if (reverse == x) {
            return true;
        }
        x = x / 10;
        if (reverse == x) {
            return true;
        }
    }
    return false;
}

Solution中的写法和我不太一样，是在循环结束后再判断：

public boolean isPalindrome(int x) {
    if(x < 0 || (x > 0 && x % 10 == 0)) return false;
    int num = 0;
    while(x > num){
        num = num * 10 + x % 10;
        x = x / 10;
    }

    // To distiguish the length of the integer is even or odd.
    if(x == num || x == num / 10) return true;
    else return false;
}

2020年6月版本

2020 年每日一题遇到。
需要注意的点：
1、反转一半后要同时比较 reverse == x 和 reverse == x/10 ，因为回文数的长度可能是奇数比如 121，也可能是偶数比如 11
2、大于 0 的 10 的倍数（也就是末尾有 0 的）都不可能是回文数，直接排除，否则后续算法无法判断
3、负数都不是回文数。

时间复杂度 O(logn)，空间复杂度 O(1)

private static class SolutionV202006 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10) == 0) {
            return x == 0 ? true : false;
        }
        // x 的逆序数
        int reverse = 0;
        while (reverse < x) {
            reverse = reverse * 10 + x % 10;
            if (reverse == x || reverse == (x / 10)) {
                return true;
            }
            x /= 10;
        }
        return false;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_009_PalindromeNumber.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_009_PalindromeNumber.java

---