leetcode解题: Palindrome Number (9)

发表于 | 分类于

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

click to show spoilers.

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： Reverse integer O（N）， N is the number of digits

用一个循环来反转数字，最后比较数字和反转的是否相等即可。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        
        int copy = x;
        int re = 0;
        while (x != 0) {
            re = re*10 + x % 10;
            x /= 10;
        }
        if (copy == re) {
            return true;
        } else {
            return false;
        }
    }
};

Java

1

解法2： Without overflow

比较最左边和最右边的两个数，这样就不会有overflow的问题了。 取得左边的数的时候我们需要的是一个除数，这个可以先用O(N)的时间求出。
然后每次求出最右位和最左位。然后每次消掉两位数，相应的div也要缩小100
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        
        int div = 1;
        while ( x / div >= 10) {
            div *= 10;
        }
        
        while (x != 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) {
                return false;
            }
            x = (x % div) / 10; // 消掉两位
            div /= 100;	// 除数缩小100
        }
        return true;
        
    }
};