回文数的五种解法

• • • • • 个人微信公众号：AI研习图书馆，欢迎关注~
• 一、题目描述
• 二、题目解析
• • 1. 解题思路
  • 2. Python实现

个人微信公众号：AI研习图书馆，欢迎关注~

深度学习知识及资源分享，学习交流，共同进步~

一、题目描述

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

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

进阶:

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

二、题目解析

1. 解题思路

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

1. 转成字符串:
   a. 双向队列
   b. 双指针
2. 不转字符串:
   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  Falsereturn True# 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的)# 复杂度: O(n)def isPalindrome(x: int) -> bool:lst = list(str(x))L, R = 0, len(lst)-1while L <= R:if lst[L] != lst[R]:return  FalseL += 1R -= 1return True# 方法三: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数# 复杂度: O(n)def isPalindrome(self, x: int) -> bool:"""模仿上面字符串的方法:分别取'第一位的数'与'第二位的数'对比(弊端是:频繁计算,导致速度变慢)(下面的方法三只反转一半数字,可以提高性能)"""if x < 0:return Falseelif x == 0:return Trueelse:import mathlength = int(math.log(x, 10)) + 1L = length-1print("l = ", L)for i in range(length//2):if x // 10**L != x % 10:return Falsex = (x % 10**L) //10L -= 2return True# 方法四: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数# 复杂度: O(n)def isPalindrome(self, x: int) -> bool:"""只反转后面一半的数字!!(节省一半的时间)"""if x < 0 or (x!=0 and x%10==0):return Falseelif x == 0:return Trueelse:import mathlength = int(math.log(x, 10)) + 1reverse_x = 0for i in range(length//2):remainder = x % 10x = x // 10reverse_x = reverse_x * 10 + remainder# 当x为奇数时, 只要满足 reverse_x == x//10 即可if reverse_x == x or reverse_x == x//10:return Trueelse:return False# 方法五: 进阶:不将整数转为字符串来解决: 不使用log函数# 复杂度: O(n)def isPalindrome(self, x: int) -> bool:"""只反转后面一半的数字!!(节省一半的时间)"""if x < 0 or (x!=0 and x%10==0):return Falseelif x == 0:return Trueelse:reverse_x = 0while x > reverse_x:remainder = x % 10reverse_x = reverse_x * 10 + remainderx = x // 10# 当x为奇数时, 只要满足 reverse_x//10 == x 即可if reverse_x == x or reverse_x//10 == x:return Trueelse:return Falsex = 10
x = 10001
print(Solution().isPalindrome(x))

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

您的支持，是我不断创作的最大动力~

欢迎点赞，关注，留言交流~

深度学习，乐此不疲~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！