LeetCode题解：回文数

题目描述

给你一个整数x，如果x是一个回文整数，返回true；否则返回false。
回文数是指正序度和倒叙读都是一样的整数。
如 121就是回文数，-121不是，123也不是。

示例

• 示例1
  输入：x=121
  输出：true
• 示例2
  输入：x=-121
  输出：false

实现思路

首先，我们要处理一些临界情况。所有的负数都不是回文数。除了0以外，其他以0结尾的数都不是回文数。
然后，我们来考虑如何反转后面的数字。
对于数字1221，如果执行1221%10，我们将得到最后一位数字1，要得到倒数第二位数字，我们可以先通过除以10把最后一位数字从1221中除掉，1221/=10->122，再求出上一步的结果除以10的余数122%10=2，就可以得到倒数第二位的数字。如果我们把最后一位数字乘以10，再加上倒数第二位数字，1*10+2=12，就得到了我们想要反转后的数字。如果继续这个过程，我们将得到更多位反转数字。

class Solution {
    public boolean isPalindrome(int x) {
        //负数肯定不是回文数
        //如果最后一个数为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;
        }

        return x==revertedNumber||x==revertedNumber/10;
    }
}

复杂度分析

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