【Leetcode】【Easy】Palindrome Number

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

判断一个整数是不是回文整数（例12321）。不能使用多余的空间。

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.

一些提示：

复数不是回文；如果你希望将整数转为字符串，注意不要使用多余的空间；

如果你希望反转整数，请注意“反转”可能导致溢出。你如何解决这个问题？

思路1：

可将此数按位从低到高依次取出，再从高到低反向排列，得到的新数字和原数字比较，一致则是回文数，否则不是。

至于提示中提到反转整数可能会出现int越界的问题，在此题中不会出现。因为如果一个int是回文整数，那么它和自身的反转相等，因此反转后不会越界。如果一个int不是回文数，反转后出现越界的情况，也不会影响结果的判定。

class Solution {
public:
    bool isPalindrome(int x) {
        int res = 0;
        int tmp_x = x;
        
        if (x<0) 
            return false;
        
        while (tmp_x != 0) {
            res = res * 10 + tmp_x % 10;
            tmp_x = tmp_x / 10;
        }
        
        if (res == x) {
            return true;
        } else {
            return false;
        }
        
    }
};

思路2：

可以将整数中，需要进行比较的首尾数字，不断取出并比较。

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        
        int sig = 1;
        
        while (x / sig >= 10) {
            sig *= 10;
        }
        
        while (x!=0) {
            if (x / sig == x % 10) {
                x = x % sig / 10;
                sig /= 100;
            } else {
                return false;
            }
        }
        
        return true;
    }
};

上面代码在函数中对x进行了修改，为了避免x被修改：

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        
        int high = 1, low = 1;
        
        while (x / high >= 10) {
            high *= 10;
        }
        
        while (high > low) {
            if (x / high % 10 == x / low % 10) {
                high /= 10;
                low *= 10;
            } else {
                return false;
            }
        }
        
        return true;
    }
};

附录：

算法中“不使用多余空间”的含义