9.回文数

作者 ： XiaXinyu
日期 ：2021-09-29

判断一个数字反转后是否和反转前相等，例如12321反转后仍然是12321，所以12321是一个回文数

将数字反转后比较是否和原数字相等，数字反转的思路与第七题是一致的

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false; //因为负数前面带有符号，所以不可能是回文数
        long ans = 0; // 将ans 定义为long型是为了防止反转后出现溢出
        long x1 = x; // 用x1来存储x，因为while循环结束后x为0
        while(x != 0){
            ans = ans * 10 + x % 10;
            x /= 10;
        }

        return x1 == ans ? true : false;
    }
}

时间复杂度 ：O(n) n为数字的位数

空间复杂度 ：O(1)

在题解一中，将整个数字进行了反转，实际上只需将数字的后半部分进行反转即可

若反转后半部分的得到的数字与前半部分数字相等，则x是回文数

重点在于怎么判断什么时候反转了一半数字呢，只需将题解一代码中的while的循环条件改成(x < ans)即可

当x的位数为奇数时，x的中位数不影响x是否是回文数的判断，所以将ans / 10在与x比较即可

还需要处理一些边界情况
1.若x为负数，则x不是回文数

2.若x的末位是0且x不等于0，则x不是回文数

• 对第二种情况进行简单的证明

  反证法：假设x的末位是0且x不等于0，则x是回文数，那么由回文数的性质可知，x的首位和末尾数相等也是0，那么x一定等于0，与假设相矛盾，所以x不可能是回文数

• 证毕

        class Solution {
    public boolean isPalindrome(int x) {

        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 去除处于中位的数字。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

时间复杂度 ：O(n) n为x的后半部分数字位数

空间复杂度 ：O(1)