LeetCode-9 回文数

发表于 | 分类于 | 评论数： | 阅读次数：

题目：回文数

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

示例 1:

1
2
输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

思路

该提如果使用字符串解决，那是相当方便的，可直接通过字符串的切片[::-1]获得反转的字符串进行比较即可，也无需判断正负号的问题：

1
2
3
4
5
6
7
class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)[::-1]
        if s == str(x):
            return True
        else:
            return False

既然进阶中要求不用字符串，那么如何获取反转数字呢？其实也很简单，对原数字进行%10取余，对反转数字不停的*10加上余数，即可。大体思路如下：

  • 先判断特殊情况，负数，最后一位为0的非0数肯定不是回文数，直接返回
  • 获取反转数字：
    • 初始化反转数字reversedNum=0
    • x%10获取个位数字
    • revservedNum进位再加上x的个位数字
    • x=x/10
  • 比较反转数字与原数字即可

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 ==0 and x != 0):
            return False
        reversedNum = 0
        num = x
        while num:
            reversedNum = reversedNum * 10 + num % 10
            num //= 10
        if reversedNum == x:
            return True
        else:
            return False

优化方法

在上述计算反转数字中，其实没有必要获取全部反转数字reversedNum，只需要计算到一半，然后比较反转数字与剩余的x即可。

如果x个位数为偶数，那么reversedNum==x

如果为奇数，那么reversedNum//10 == x

比如x = 12321，根据上述逻辑，计算到reversedNum=123时，x=12，满足奇数条件

比如x = 1221，根据上述逻辑，计算到reversedNum=12是，x=12，满足偶数条件

那么怎么判断已经计算到一半了呢：

由于反转过程中是对reversedNum的进位，和x的退位，当计算到一半时，reversedNum必然大于x。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 ==0 and x != 0):
            return False
        reversedNum = 0
        while x > reversedNum:
            reversedNum = reversedNum * 10 + x % 10
            x //= 10
        if x == reversedNum or x == reversedNum // 10:
            return True
        else:
            return False

如果大家有更好的方法，欢迎一起探讨。