leetcode 每日一题 9. 回文数

 

leetcode 每日一题   9. 回文数

1.整数转字符串

思路:

将整数变为字符串,然后翻转字符串,如果翻转后的字符串和原字符串一致,则为回文数。

例如:

123 -> '123' ,翻转后 '321',因为'321' != '123',所以不是回文数

202 -> '202' , 翻转后'202',因为'202' == '202',所以是回文数

代码:

class Solution:
    def isPalindrome(self, x: int) -> bool:
        str_num = str(x)
        return True if str_num == str_num[::-1] else False

2.整数前后比较

思路:

首先,我们应该处理一些临界情况。所有负数都不可能是回文

例如:-123 不是回文,因为 - 不等于 3。所以我们可以对所有负数返回 false。

然后让我们来考虑如何反转后半部分的数字。对于数字 1221,如果执行 1221 % 10,我们将得到最后一位数字 1,要得到倒数第二位数字,我们可以先通过除以 10 把最后一位数字从 1221 中移除,1221 // 10 = 122,再求出上一步结果除以 10 的余数,122 % 10 = 2,就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10,再加上倒数第二位数字,1 * 10 + 2 = 12,就得到了我们想要的反转后的数字。如果继续这个过程,我们将得到更多位数的反转数字。

最后要讨论如何确定反转数字的位数已经达到原始数字位数的一半?我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。这里考虑奇偶性,如果原始数字等于反转后数字或者等于反转后数字除以10,均可认为为回文数。

例如:

x = 121  revertedNumber = 0

①x>revertedNumber, revertedNumber = 0 * 10 + 121 % 10 = 1   x = 121 // 10 = 12

①x>revertedNumber, revertedNumber = 1 * 10 + 12 % 10 = 12   x = 12 // 10 = 1

①x<revertedNumber, 由于 x == revertedNumber//10 ,所以原数字为回文数

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

 

 

    

上一篇:LeetCode 回文数


下一篇:回文数