编写通过所有测试案例的代码并不简单,通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例,但如果不了解代码背后的思考过程,那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷,是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正,因为我知道我的观点可能并不完全正确,您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示,我也会感到非常荣幸。同时,我也希望我的分享能够激发您的灵感和思考,让我们一起在编程的道路上不断前行~
给你一个整数 x
,如果 x
是一个回文整数,返回 true
;否则,返回 false
。
回文数:正序(从左向右)和倒序(从右向左)读都是一样的整数。
121
是回文,而 123
不是。示例 1:
示例 2:
示例 3:
根据示例,我们可以总结出以下规律:
因此,对于符合规律1/2的输入,我们可以先通过if
语句直接返回False
;
即:
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0 or (x % 10 == 0 and x != 0):
return False
题意告诉我们,进阶做法是不能基于字符串解决【回文数】这个问题 ===> 基于字符串的做法应该比较简单且容易上手。
实际上,基于字符串的解法确实非常简单,
完整代码如下:
class Solution:
def isPalindrome(self, x: int) -> bool:
x_str = str(x) # 将整数x转换为字符串x_str
return x_str == x_str[::-1]
从代码中可以看出,我们只需要三步即可解决【回文数】问题:
str()
将整数x
强制类型转换为字符串x_str
;[::-1]
将字符串反转;True
,否则返回False
;运行结果:
问题1:如果题目不提示【字符串】解法,一般我们会想到什么方法呢?
我们一般不会离开"整数"这个范畴去解决问题 ===> 正常步骤应该是:
x
进行反转,变成另一个整数x_reverse
;x
和反转后的x_reverse
,判断这两个整数是否相等,相等则是回文数,返回True
,否则返回False
;完整代码如下:
class Solution:
"""
判断一个整数是否是回文数。
Args:
x (int): 待判断的整数。
Returns:
bool: 如果x是回文数,则返回True;否则返回False。
"""
def isPalindrome(self, x: int) -> bool:
# 边界条件
if x < 0 or (x % 10 == 0 and x != 0):
return False
# 初始化反转后的数为0
x_reverse = 0
# 保存原始的x值,以便后面与反转后的数进行比较
x_tmp = x
# 当x_tmp大于等于1时执行循环,将x_tmp的个位数逐个取出并放到反转后的数中
while x_tmp >= 1:
# 当前取出的个位数为 x_tmp % 10
x_reverse = x_reverse * 10 + x_tmp % 10 # 当前反转数乘以10 + 当前取出的个位数
# 将x_tmp除以10,去掉当前个位数
x_tmp = x_tmp // 10
return x_reverse == x
运行结果:
复杂度分析
细节1:尽管将整数完全反转可以通过所有测试用例,但如果题目不仅要求输入x
满足 -231 <= x
<= 231 - 1,而且要求反转后的x_reverse
也满足 -231 <= x_reverse
<= 231 - 1,那么将整数完全反转可能会导致x_reverse
溢出。
由于231 - 1 = 2147483647,如果整数x=2147483647
,那么x_reverse=7463847412
> 231 - 1 ? x_reverse溢出。
问题2:为什么把x=2147483647
作为测试用例时,将整数完全反转的算法仍然能通过呢?
在Python3中,整数类型只有int,没有限制大小!!! ? 理论上,Python 3中的整数没有上限(只要不超出内存空间)? 将整数完全反转的算法面对有溢出风险的输入仍能顺利运行。
实际上,方案2仍然有进一步优化的空间,因为我们一直没有使用回文数的一个重要性质:对称性 ? 我们实际上只需要反转一半的数字,就可以判断输入x
是否为回文了。