题目描述

[EN | CN]

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

1
2
输入: 121
输出: true

示例 2:

1
2
3
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗?

解法 1:取一半

最直接想到的做法就是转成字符串然后倒转对比就行,但是这样的代价比较大,而且题目要求不转为字符串,那么我们尝试直接从 int 类型入手来判断回文。

首先可以想到我们取第一个数跟最后一个数来对比,然后往中间「推」就行,但是取第一个数也没有能直接取的办法。那么我们再换个思路,从后往前取,取到数字的一半位置的时候,我们开始跟剩余的数字对比。

注意,什么时候才可以确定「取到了数字的一半位置」?应该是当我们已经取出的数字大于(原数字有奇数位)或等于(原数字有偶数位)剩余数字的时候。

假设原整数的位数为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False

        rev = 0
        while x > rev:
            rev = rev * 10 + x % 10
            x //= 10
        return x == rev or x == rev // 10
  • 执行用时:84 ms,在所有 Python3 提交中击败了 71.68% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 5.88% 的用户。