LeetCode 009 — Palindrome Number

请注意,本文编写于 181 天前,最后修改于 181 天前,其中某些信息可能已经过时。

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。

总结

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

参考资料

添加新评论