LeetCode:整数反转/回文数判断

题目：

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

输入: 123

输出: 321

输入: -123

输出: -321

输入: 120

输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

思路：这道题较简单，看到这个第一下想到的是用队列模型，队列模型属于先入先出型，正好实现。

主要问题在于溢出的判断上。

int reverse(int x) {
    if(x==0||x<=INT_MIN||x>INT_MAX)
    {
        return 0;
    }   
     queue<int> qint;
     int x0=abs(x);
     int flag = x/x0;
     while(x0)
     {
         int tmp = x0%10;
         qint.push(tmp);
         x0/=10;
     }
    long int revnum=0;
    while(!qint.empty())
    {
        int bit=qint.front();
        qint.pop();
        revnum=revnum*10+bit;
        if((revnum>INT_MAX)&&flag)
            return 0;
        if((revnum>(INT_MAX+1))&&(!flag))
            return 0;
    }
     return (int)revnum*flag;
    }
           

这里主要问题在当输入INT_MIN，-2147483648时，如果直接取绝对值，范围会超出32位整数范围。 又考虑到这种情况下反转后也应该直接返回0 ，所以直接放在开头判断了。

本代码冗余的是先入队列再出队列，两次循环加大了时间复杂度，其实可以优化为一次循环的。

因为先入先出模型是一 一对应的，不同于先入后出，需要先保存。

本例用了64位整数存储运算结果，这样就可以根据计算的中间结果判断是否溢出了。

int reverse(int x) {
    if(x==0||x<=INT_MIN||x>INT_MAX)
    {
        return 0;
    }   
     queue<int> qint;
     int x0=abs(x);
     int flag = x/x0;
     long int revnum=0;
     while(x0)
     {
         int tmp = x0%10;
         revnum=revnum*10+tmp;
        if((revnum>INT_MAX)&&flag)
            return 0;
        if((revnum>(INT_MAX+1))&&(!flag))
            return 0;
         x0/=10;
     }
     return (int)revnum*flag;
    }
           

效率大幅提升 。

进一步优化，c++中负数的整除余除与正数是一样的，恰好能分离出我们需要的每一位数。所以不必在一开始求绝对值。

也不必用64位整数存中间过程，只要在计算过程中判断下次运算开始前是否会超限，再进行计算即可。

int reverse(int x) {
    if(x==0||x<=INT_MIN||x>INT_MAX)
    {
        return 0;
    }   
    int revnum=0;
    while(x)
     {
         int tmp = x%10;
        if((revnum>INT_MAX/10)||((revnum==INT_MAX/10)&&(tmp>7)))
            return 0;
        if((revnum<INT_MIN/10)||((revnum==INT_MIN/10)&&(tmp<-8)))
            return 0;
        revnum=revnum*10+tmp;
         x/=10;
     }
     return revnum;
    }
           

执行用时 :

0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :

8.2 MB, 在所有 C++ 提交中击败了79.34%的用户

顺着这个思路可以解决整数的回文数的问题。

断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

输入: 121

输出: true

示例 2:

输入: -121

输出: false

解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

只判断一半即可

bool isPalindrome(int x) {
        if(x<0||x>2147447412)
            return false;
        int renum=0;
        int num=x;
        while(x)
        {
            int tmp=x%10;
            if((renum>214744741)||((renum==214744741)&&(tmp!=2)))
            {
                 return false;
            }   
            renum = renum*10+tmp;
            x=x/10;
        }
        return (num==renum)?true:false;
    }
           

再进一步优化，只比较一半就可以了。如何判断到达一半了呢？得到的数字比之前的数字大了，就过一半了。

还有就是末位为0也可以直接返回false

bool isPalindrome(int x) {
        if(x<0||x>2147447412||(x%10==0&&x!=0))
            return false;
        int renum=0;
        while(x>renum)
        {
            renum = renum*10+x%10;
            x=x/10;
        }
        return (x==renum)||(x==renum/10);
    }
           

奇数位如何判断呢？ 判断整除10后与x是否相等。