LeetCode:9. Palindrome Number

Posted on In Disqus:

9. Palindrome Number

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

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. 不能为负
  2. 最好不要转为string来判断
  3. 反转之后要注意int的容量
  4. 如果反转时overflow则一定不是回文

code

my

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int i = 0, xori = x;
        long long rev = 0;
        while(x != 0)
        {
            i = x % 10;
            rev = (rev * 10) + i;
            x /= 10;
        }
        return rev == xori;
    }
};

@喜刷刷

通过overflow判断，可以将rev类型降低为int

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        int res=0, y=x;
        while(y) {
            if(abs(res)>(INT_MAX/10)) return false;
            res = res * 10 + y % 10;
            y /= 10;
        }
        return res==x;
    }
};

比较最高位和最低位

比较最高位与最低位的数字：如果不同则不是回文，如果相同，则去掉最高和最低位，继续判断。直到所有位数字都被去掉，则一定是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        int y = 1;
        while(x/y>=10)
            y *= 10;
 
        while(x) {
            if(x/y != x%10) return false;
            x = (x % y)/10;
            y /= 100;
        }
        return true;
    }
};