LeetCode高频算法面试题 - 009 - 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

题目难度: ★, 简单

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：

-2^31 <= x <= 2^31 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

代码实现

tips: 以下代码是使用Go代码实现的不同解法, 文章最后可以看C++、C、Java、Python实现

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    div := 1
    // 得到对应位数的最小值, 例如：6543，那么div的值就是1000
    for x / div >=  10 {
        div *= 10
    }
    for x != 0 {
        // 得到左边第一位的值
        left := x / div
        // 得到右边最后一位的值
        right := x % 10
        if left != right {
            return false
        }
        // 去掉第一位和最后一位
        // 例如：（ 6543 - 6 * 1000 ）/ 10 = 54
        x = (x - left * div) / 10

        // 因为去掉了最右边和最左边两位，因此div也相应的调整
        div /= 100
    }
    return true
}

其他语言实现

1、Java

主要思路:

• 如果是负数则一定不是回文数，直接返回 false
• 如果是正数，则将其倒序数值计算出来，然后比较和原数值是否相等
• 如果是回文数则相等返回 true，如果不是则不相等 false
• 比如 123 的倒序 321，不相等；121 的倒序 121，相等

important: 旋转后的数字可能越界， 比如1234567899，旋转后就是9987654321大于了2^31了。当出现越界的情况就时，可以肯定这个数字就不是回文数。

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
            return false;
        int cur = 0;
        int num = x;
        while(num != 0) {
            cur = cur * 10 + num % 10;
            num /= 10;
        }
        return cur == x;
    }
}

2、Python3

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        res, y = 0, x
        while y != 0:
            res = res*10 +y%10
            y //=10
        return res == x

3、C++

class Solution {
public:
    bool isPalindrome(int x) 
    {   
        if(x<0)
            return false;   
        
        vector<int> v;    
        while(x>0)
        {
            int a=x%10;  
            v.push_back(a);
            x=x/10;
        }

        // 两头开始比较向量中的数字
        int len=v.size();
        int j=0;
        while(j<len/2)
        {
            if(v[j]!=v[len-j-1])
                return false;
            j++;
        }
        return true;
    }
};

几种语言运行效果对比

也欢迎关注我的公众号: 漫步coding。 一起交流, 在coding的世界里漫步。