LeetCode题解-回文数的五种Python解法

Ethel ·

更新时间:2024-09-21

· 914 次阅读

回文数的五种解法一、题目描述二、题目解析1. 解题思路2. Python实现 一、题目描述

题目：9.回文数
难度：简单

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

二、题目解析 1. 解题思路

五种解法
解题思路: (五种实现方法)

转成字符串:
a. 双向队列
b. 双指针不转字符串:
a. 模拟字符串的双向队列(使用math库的log函数获取整数的位数)
b. 反转后面一半的整数(使用math库的log函数获取整数的位数)
c. 反转后面一半的整数(不适用log函数) (通过原整数x 与 reverse_x 的大小判断) 2. Python实现

class Solution:
    # 方法一: 将int转化成str类型: 双向队列
    # 复杂度: O(n^2) [每次pop(0)都是O(n)..比较费时]
    def isPalindrome(x: int) -> bool:
        lst = list(str(x))
        while len(lst) > 1:
            if lst.pop(0) != lst.pop():
                return  False
        return True
    # 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的)
    # 复杂度: O(n)
    def isPalindrome(x: int) -> bool:
        lst = list(str(x))
        L, R = 0, len(lst)-1
        while L  bool:
        """
        模仿上面字符串的方法:分别取'第一位的数'与'第二位的数'对比
                        (弊端是:频繁计算,导致速度变慢)(下面的方法三只反转一半数字,可以提高性能)
        """
        if x  bool:
        """
        只反转后面一半的数字!!(节省一半的时间)
        """
        if x  bool:
        """
        只反转后面一半的数字!!(节省一半的时间)
        """
        if x  reverse_x:
                remainder = x % 10
                reverse_x = reverse_x * 10 + remainder
                x = x // 10
            # 当x为奇数时, 只要满足 reverse_x//10 == x 即可
            if reverse_x == x or reverse_x//10 == x:
                return True
            else:
                return False
x = 10
x = 10001
print(Solution().isPalindrome(x))

码字不易，欢迎点赞，关注，精彩不断，好题连连~~~

作者：算法之美DL

leetcode 回文数 Python

1024 个赞