leetcode | 9.回文数

9.回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
题目链接

思路

1.使用栈判断是否回文
先将每位数字依次入栈，再将栈中的所有数字依次出栈，如果入栈的数字序列与出战的数字序列相同，则该数为回文数。
2.将整数x转化为字符串
将整数x转化为字符串，将字符串反转，如果原字符串与反转字符串相等，则该数为回文数。
3.反转一半数字
反转后一半数字，并将其与前半部分数字进行比较，如果二者相同，则该数为回文数。
如何知道反转数字的位数已经达到原始数字位数的一半？当原始数字小于或等于反转后的数字时，就意味着我们已经处理了
一半位数的数字了。

代码

class Solution(object):
    def isPalindrome2(self, x):
        """
        使用栈实现回文
        
        先将每位数字依次入栈，再将栈中的所有数字依次出栈，如果入栈的数字序列与出战的数字序列相同，则该数为回文数。
        """
        if x < 0:  # 负数肯定不是回文数
            return False
        xCopy = x
        stack = list()
        while x != 0:
            stack.append(x % 10)
            x = x // 10
            
        stack = stack[::-1]  # 从个位数开始取每位数字比较方便，但是入栈的数字序列与原数字序列相反，故反转栈
        
        revertedNumber = 0
        while stack:
            revertedNumber = revertedNumber * 10 + stack.pop()
        
        if xCopy == revertedNumber:
            return True
        else:
            return False
    
    def isPalindrome1(self, x):
        x = str(x)
        return x == x[::-1]
    
    def isPalindrome(self, x):
        """
        特殊情况：
        1.当x<0时，x不是回文数
        2.如果数字的最后一位是0，为了使该数字为回文，则
          其第一位数字也应该是0，只有0满足
        """
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        
        revertedNumber = 0
        while x > revertedNumber:
            revertedNumber = (revertedNumber * 10) + (x % 10)
            x //= 10
            
        # 当数字长度为奇数时，我们可以通过revertedNumber/10去除位于中位的数字。
        # 例如，当输入为12321时，在while循环末尾我们可以得到x=12，revertedNumber=123,
        # 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber or x == revertedNumber // 10
    
if __name__ == "__main__":
    slt = Solution()
    # res = slt.isPalindrome(12321)
    # res = slt.isPalindrome1(12321)
    res = slt.isPalindrome2(12321)
    print("是回文数" if res else "不是回文数")