Palindrome Number

https://leetcode.com/problems/palindrome-number/

给定一个整型数，判断这个数是否为回文数

我们根据例子很容易得出，负数不是回文数，一位正整数肯定是回文数。

Solution1

首先用最简单的方法，把数字转换成字符串，从两边向中间依次判断对应位的数字是否相等。

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

        if( x == 0) {
            return true;
        }

        std::string str = to_string(x);
        int middle = str.length()/2;
        for (int i = 0; i < middle; ++i) {
            if(str[i] != str[str.length() - 1 - i]) {
                return false;
            }
        }

        return true;
    }
};

Solution2

题目的最后问能否不通过转换成字符串的方式解决这个问题，那就尝试一下吧。不通过字符串，其实我们还是要从两边到中间依次比较对应位的数字。那么问题来了，如何依次取得左右两边的数字呢？

我们以 12341 这个数字为例，想要获得最低位数字 1 很简单只要12341 % 10就得到了。那么如何获得最高位数字 1 呢？我们发现12345/10000 -> 1，也就是说用这个数除以 10^4 就行了，其中的 4 是 12341 的位数 5 减去 1。我们可以通过循环 / 10 的方式取得一个数字的位数。

12341 % 10 -> 1
12341 / (10 ^ 4) -> 1

当我们比较取得的最高位和最低位之后，发现是相等的，要继续循环，需要把原来的这个数字掐头去尾。我们来看看如何实现：

12341 % (10 ^ 4) -> 2341
2341 / 10 -> 234

也就是说，我们可以通过把这个数先 % (10 ^ 4) 再 / 10 来实现掐头去尾。

上完整代码：

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

        if( x < 10) {
            return true;
        }

        int div = 1;
        int x1 = x;
        while(x1 >= 10) {
            div *= 10;
            x1 /= 10;
        }

        while (x > 0) {
            int l = x / div;
            int r = x % 10;
            if (l != r) {
                return false;
            }
            x = x % div / 10;
            div /= 100;
        }

        return true;
    }
};

这里我们考虑一种特殊情况，比如 x 是 100341，那么掐头去尾之后，x 变成了 34，而不是 0034，这会不会对我们的结果造成影响呢？

我们发现执行第二次循环的时候 div = 10000，那么 34 / 10000 -> 0，也就是说我们还是取到了正确的数字 0 而不是3 。这得益于我们保留了之前的 div 的值然后每次 / 100，而不是每次都重新计算 x 的位数。

执行第三次循环的时候 x = 3, div = 100，那么3 / 100 -> 0，我们依然取得了正确的数字，也就是说我们上面的解法是正确的。

提交之后成功通过，运行时间 44 ms。

Solution2 优化

我们观察一下上面解法中获取 x 位数的部分：

int div = 1;
int x1 = x;
while(x1 >= 10) {
    div *= 10;
    x1 /= 10;
}

我们发现我们每次运算的时候都要把 div * 10 然后把 x1 / 10。那为什么不把这两部分结合起来直接用 while(x / div >= 10) 来当循环条件呢？

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

        if( x < 10) {
            return true;
        }

        int div = 1;
        while(x / div >= 10) {
            div *= 10;
        }

        while (x > 0) {
            int l = x / div;
            int r = x % 10;
            if (l != r) {
                return false;
            }
            x = x % div / 10;
            div /= 100;
        }

        return true;
    }
};

再提交一下，这次的运行时间是 32 ms。

总结

虽然是一道看起来非常简单的题目，用转换成字符串的方式实现可能花不了几分钟的时间，但是不用字符串转换的方式要花点时间琢磨。这一题完整实现下来我自己也有新的收获，挺开心的。

参考资料