Leetcode 9. 回文数

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
Try it on Leetcode

输入示例

示例 1

输入: 121
输出: true

示例 2

输入: -121
输出: false
解释: 从右向左读为 121-, 因此不是回文数

示例 3

输入: 10
输出: false
解释: 从右向左读为 01, 因此不是回文数

解题思路：反转一半数字

映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文数。但是，如果反转后的数字大于Integer.MAX_VALUE，就会遇到整数溢出的问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，可以考虑只反转int数字的一半。如果输入的是回文数，那么其后半部分反转后应该与原始数字的前半部分相同。

Java 实现

class Solution {
    public boolean isPalindrome(int x) {
        /**
         * if x < 0 or end up with 0 ( except 0 itself )
         * then return false
         */
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int reverseNumber = 0;
        while (x > reverseNumber) {
            reverseNumber = reverseNumber * 10 + x % 10;
            x /= 10;
        }

        return x == reverseNumber || x == reverseNumber / 10;
    }
}

Go 实现

func isPalindrome(x int) bool {
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }

    reverseNumber := 0
    for x > reverseNumber {
        reverseNumber = reverseNumber * 10 + x % 10
        x /= 10
    }

    return x == reverseNumber || x == reverseNumber / 10
}

复杂度分析

时间复杂度： $O(\log_{10}(n))$ 。对于每次迭代，需要将输入除以10
空间复杂度： $O(1)$

参考文章

9. Palindrome Number | Leetcode

Leetcode 9. 回文数 | 苏易北

题解 - 9. 回文数 | Leetcode力扣

🚩推荐阅读（由hexo文章推荐插件驱动）