凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 9. Palindrome Number

分类:algorithm| 发布时间:2016-06-28 09:41:00


题目

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

严格来说,不使用额外空间是无法完成任务的, 总需要额外的一到两个 integer 或者使用递归的话会使用额外的栈空间。

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        // equivalence pow(10, log10(x))
        int p = 1;
        while (x / p >= 10) {
            p *= 10;
        }

        while (x) {
            if (x / p != x % 10) {
                return false;
            }

            x -= (x % 10) * p;
            x /= 10;
            p /= 100;
        }

        return true;
    }
};

依照定义逐次对比最高位和最低位的数字。

解法 2

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        int revhalf = 0, slow = x, fast = x;
        while (fast) {
            revhalf = revhalf * 10 + slow % 10;
            slow /= 10;
            fast /= 100;
        }

        return slow == revhalf || slow == revhalf / 10;
    }
};

翻转数字的一半然后对比。

解法 3

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int mirror = 0;
        int cache = x;
        while (x) {
            mirror = mirror * 10 + x % 10;
            x /= 10;
        }

        return mirror == cache;
    }
};

翻转数字然后对比。

解法 4

class Solution {
public:
    bool isPd(int &xd, int xn) {
        if (xn / 10 == 0) {
            return (xd % 10) == xn;
        } else {
            return isPd(xd, xn/10) && (xn % 10) == (xd=xd/10) % 10;
        }
    }

    bool isPalindrome(int x) {
        if (x < 0) return false;
        return isPd(x, x);
    }
};

这个方法的好处是貌似符合了不能用额外空间的限制(没有显式定义变量), 而是通过递归的方法完成任务。