class Solution {
public:
bool isPalindrome(int x) {
}
};
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
121 是回文，而 123 不是。
示例 1：
输入：x = 121 输出：true
示例 2：
输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
进阶：你能不将整数转为字符串来解决这个问题吗？
相似题目
原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-28 11:04:37
class Solution:
# 方法一: 将int转化成str类型: 双向队列
# 复杂度: O(n^2) [每次pop(0)都是O(n)..比较费时]
def isPalindrome1(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 isPalindrome2(x: int) -> bool:
lst = list(str(x))
L, R = 0, len(lst)-1
while L <= R:
if lst[L] != lst[R]:
return False
L += 1
R -= 1
return True
# 方法三: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
# 复杂度: O(n)
def isPalindrome3(self, x: int) -> bool:
"""
模仿上面字符串的方法:分别取'第一位的数'与'第二位的数'对比
(弊端是:频繁计算,导致速度变慢)(下面的方法三只反转一半数字,可以提高性能)
"""
if x < 0:
return False
elif x == 0:
return True
else:
import math
length = int(math.log(x, 10)) + 1
L = length-1
print("l = ", L)
for i in range(length//2):
if x // 10**L != x % 10:
return False
x = (x % 10**L) //10
L -= 2
return True
# 方法四: 进阶:不将整数转为字符串来解决: 使用log来计算x的位数
# 复杂度: O(n)
def isPalindrome4(self, x: int) -> bool:
"""
只反转后面一半的数字!!(节省一半的时间)
"""
if x < 0 or (x!=0 and x%10==0):
return False
elif x == 0:
return True
else:
import math
length = int(math.log(x, 10)) + 1
reverse_x = 0
for i in range(length//2):
remainder = x % 10
x = x // 10
reverse_x = reverse_x * 10 + remainder
# 当x为奇数时, 只要满足 reverse_x == x//10 即可
if reverse_x == x or reverse_x == x//10:
return True
else:
return False
# 方法五: 进阶:不将整数转为字符串来解决: 不使用log函数
# 复杂度: O(n)
def isPalindrome(self, x: int) -> bool:
"""
只反转后面一半的数字!!(节省一半的时间)
"""
if x < 0 or (x!=0 and x%10==0):
return False
elif x == 0:
return True
else:
reverse_x = 0
while 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
golang 解法, 执行用时: 8 ms, 内存消耗: 4.1 MB, 提交时间: 2023-10-28 11:02:19
func isPalindrome(x int) bool {
// 特殊情况：
// 如上所述，当 x < 0 时，x 不是回文数。
// 同样地，如果数字的最后一位是 0，为了使该数字为回文，
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
if x < 0 || (x % 10 == 0 && x != 0) {
return false
}
revertedNumber := 0
for x > revertedNumber {
revertedNumber = revertedNumber * 10 + x % 10
x /= 10
}
// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10
}
java 解法, 执行用时: 5 ms, 内存消耗: 41.6 MB, 提交时间: 2023-10-28 11:02:03
class Solution {
public boolean isPalindrome(int x) {
// 特殊情况：
// 如上所述，当 x < 0 时，x 不是回文数。
// 同样地，如果数字的最后一位是 0，为了使该数字为回文，
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10;
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 6.1 MB, 提交时间: 2023-10-28 11:01:48
class Solution {
public:
bool isPalindrome(int x) {
// 特殊情况：
// 如上所述，当 x < 0 时，x 不是回文数。
// 同样地，如果数字的最后一位是 0，为了使该数字为回文，
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber / 10;
}
};
python3 解法, 执行用时: 68 ms, 内存消耗: 14.9 MB, 提交时间: 2022-08-10 14:42:42
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
m = str(x)
for i in range(0, len(m)):
if m[i] != m[len(m)-i-1]:
return False
return True
python3 解法, 执行用时: 312 ms, 内存消耗: N/A, 提交时间: 2018-08-22 14:22:49
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
m = str(x)
for i in range(0, len(m)):
if m[i] != m[len(m)-i-1]:
return False
return True