[leetcode02]9-回文数

题目

第9题:回文数

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

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false

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

示例 3:

输入: 10
输出: false

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

进阶:
你能不将整数转为字符串来解决这个问题吗?

思路&实现

思路:先取出各个数字变成list,再翻转;然后判断新的list与原来的是否一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isPalindrome(self, x):
"""
先取出各个数字组成list,再翻转
:type x: int
:rtype: bool
"""
li = []
if x < 0:
return False
else:
while x != 0:
li.append(x % 10)
x = int(x / 10)
return list(reversed(li)) == li

官方解释

首先,我们应该处理一些临界情况。所有负数都不可能是回文,例如:-123 不是回文,因为 - 不等于 3。所以我们可以对所有负数返回 false。

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

现在的问题是,我们如何知道反转数字的位数已经达到原始数字位数的一半?

我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。

复杂度分析

时间复杂度:O(\log_{10}(n))O(log 10 (n)), 对于每次迭代,我们会将输入除以10,因此时间复杂度为 O(\log_{10}(n))O(log10(n))。
空间复杂度:O(1)O(1)。

实现

根据官方的解释,我试着实现了一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gaunfang(self, x):
'''
用时:400ms
:param x:
:return:
'''
if x < 0:
return False
temp_x = x
y = 0
while temp_x != 0:
y = y * 10 + temp_x % 10
temp_x = int(temp_x / 10)
return y == x

其他方法

1
2
3
4
5
6
7
8
9
10
11
def reversed_str(self, x):
'''
翻转字符串
用时:446ms
:param x:
:return:
'''
if str(x) == str(x)[::-1]:
return True
else:
return False

这个方法主要是采用了字符串截取的方法,从最后逐位翻转,在判断。

题目难度

难度:简单

总结

这道题的算法难度不大,实现起来简单,但是没有想到的是,python的实现方法会是如此的简洁。看来,还是的多接触一下优秀的代码,增长一下自己的见识才行!!!

0%