LeetCode【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.

值得注意的地方就是without extra space。

代码如下：

bool isPalindrome(int x) {
    if(x<0)
        return false;
    for(int i=1;x>=10;i++)
    {
        int first =x,last=x;
        int j=0,k=0;
        last = x%10;
        for(j=0;first>=10;j++)
        {
            first=first/10;
        }
        if(first != last )
            return false;
        for(k=0;k<j;k++)
        {
            first = first*10;
        }
        x = (x-first)/10;
        if(x==0)
            return true;
        first = x;
        for(k=0;first>=10;k++)
            first = first/10;
        j = j-k-2;
        if(j!=0)
        {
            if(x<10)
                return false;
            for(k=0;k<j;k++)
            {
                int tmp=x%10;
                if(tmp!=0)
                    return false;
                x=x/10;
            }
        }
    }
    return true;
}

View Code

觉得这样写挺乱的，于是去看别人写的。发现思路一样，每次取首位两个数字，判断是否相同。

给出别人的代码：

bool isPalindrome2(int x) {
    //negative number
    if(x < 0)
        return false;

    int len = 1;
    while(x / len >= 10)
        len *= 10;

    while(x > 0)    {

        //get the head and tail number
        int left = x / len;
        int right = x % 10;

        if(left != right)
            return false;
        else    {
            //remove the head and tail number
            x = (x % len) / 10;
            len /= 100;
        }
    }

    return true;
}

View Code

一样的思路，貌似比我的巧妙了不少啊。