Palindrome Number
如果一个数字从左往右和从右往左读都相同，它就是回文数，例如 1221。给定一个整数 x，如果它是回文数，则返回 true，否则返回 false。负数永远不算回文数，因为它的负号在另一端没有对应的符号。
函数
- xinteger
- 要检查的整数，可能为负数
- 返回值boolean
- 如果 x 正反读都一样，则为真，否则为假
约束条件
-231 ≤ x ≤ 231-1- 所有负数都会返回
false。
示例
- 输入
- x = 121
- 输出
- true
- 解释
- 从后往前读，121 还是 121，所以答案是
true。
- 输入
- x = -121
- 输出
- false
- 解释
- 反向读取时，
-121会变成121-，这是不同的文本，所以答案是false。
进阶
你能在不把整数转换为字符串的情况下解决这个问题吗？
提示
逐个打开提示，每个都会多透露一点。
负数永远不可能是回文数，所以要先处理它们。
用
x % 10取出最后一位，再用整数除法除以10将它去掉。用
reversed = reversed * 10 + digit构造反转后的数字，然后将它与原数字进行比较。
题解
如果一个数字与其倒序相同，它就是回文数。把它当作文本，只需进行一次比较。如果不使用文本，重新构造整个倒序数字可能会溢出，因此只反转数字的后半部分，并将其与前半部分进行比较。
将字符串与其反转结果进行比较
思路
把这个数字写成文本，并将它与反转后的文本进行比较。负数不需要特殊处理：-121以负号开头、以数字结尾，因此永远不会等于反转后的文本121-。
每个数字对应一个字符，文本长度约为log10(x)，此处最多为 11。代价是需要额外的字符串。
算法
- 将
x转换为字符串s。 - 反转
s。 - 返回
s是否等于其反转结果。
def isPalindrome(x):
s = str(x)
# A minus sign sits only at the front, so a negative never matches its reverse.
return s == s[::-1]将数字的一半倒序
思路
x % 10 会得到最后一位数字，整除以 10 会将它移除。把 x 末尾的数字移到另一个数 half 上，就能用移除的数字构建出它们的逆序。等到 half 大于或等于 x 剩下的部分时停止：这时你已经处理了一半的数字。对于 1221，最后会得到 x = 12 和 half = 12，这是一个回文数。如果数字位数是奇数，half 还会包含中间那一位：对于 12321，最后会得到 x = 12 和 half = 123，因此要比较 x 和 half / 10。
在循环之前处理两种情况。负数永远不是回文数。末尾是 0 的数字，开头也必须是 0，但只有 0 符合这一点；如果不进行这项检查，10 最后会得到 x = 0 和 half = 1，导致 x == half / 10 错误地通过。half 最大不会超过 6 位数，因此任何整数类型都能存下它。
算法
- 如果
x是负数，或者末尾是 0 且本身不为 0，则返回false。 - 设置
half = 0。 - 当
x > half时，将half = half * 10 + x % 10，并使用整数除法将x除以 10。 - 如果
x == half（位数为偶数）或x == half / 10（位数为奇数），则返回true。
def isPalindrome(x):
if x < 0:
return False
original, reversed_num = x, 0
while x > 0:
reversed_num = reversed_num * 10 + x % 10
x //= 10
return original == reversed_num
易错点和边界情况
- 忘记处理负数。在余数保留符号的语言中，反转
-121会得到-121，检查也会通过。在 Python 中，-1 // 10的结果是-1，因此while x != 0循环永远不会结束。 - 没有排除以 0 结尾的数字。这样，反转一半数字的方法就会接受
10。0本身是回文数。 - 在 32 位整数中反转整个数字。
2147483647反转后的结果无法用 32 位整数表示。 - 在会进行分数除法的语言中使用
/。在 JavaScript 中使用Math.floor(x / 10)，在 Python 中使用//，在 R 中使用%/%，在 Dart 中使用~/。 - 循环改变
x后，仍将反转后的完整数字与x比较。保留原始数字的副本。
常见问题3
负数是回文数吗？
不对。倒着读时，-121 会变成 121-，末尾的减号在另一端没有对应的字符。因此，所有负整数都会返回 false。
为什么只反转数字的一半？
反转所有数字可能会导致 32 位整数溢出：2147483647 的反转结果比最大的 int 还大。一半的数字始终可以放得下，而且循环只需完成一半的工作。
回文数的时间复杂度是多少？
这两种方法的时间复杂度都是 O(log x)，因为数字 x 大约有 log10(x) 位，每一位只处理一次。字符串方法会为文本额外使用 O(log x) 的空间；反转一半的方法使用 O(1) 的空间。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isPalindrome(x):
# 在这里编写代码测试 #1
测试 #2
参数
x = 121
预期输出
true