9. 回文数

题目

给你一个整数 $x$ ，如果 $x$ 是一个回文整数，返回 $true$ ；否则，返回 $false$ 。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例子

1. 输入：$x=121$
   输出：$true$
2. 输入：$x=-121$
   输出：$false$
   解释：从左向右读, 为 $-121$ 。 从右向左读, 为 $121-$ 。因此它不是一个回文数。
3. 输入：$x=10$
   输出：$false$
   解释：从右向左读, 为 $01$ 。因此它不是一个回文数。

思路

1. 首尾测试

为了判断是否回文数，判断首尾是否相等，然后左指针和右指针左移和右移，可以不用计算到最后，只要在中途发现不对称就可以直接返回False，否则最后返回True。如果输入的是空字符串，也应该返回True，因为空字符串也是回文数。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

class Solution:def isPalindrome(self, x: int) -> bool:s = str(x)# 空字符串也是回文数if not s:return Truei = 0j = len(s) - 1# 这表示只要 i 不小于 j，即左指针越过右指针或者指向同一个元素，就说明是回文数。while i < j:if s[i] == s[j]:i += 1j -= 1# 只要不对称就返回Falseelse:return False# 判断完毕 返回Truereturn True

2. 数学

如果是负数，直接不是回文数；如果是正数，则将数值倒过来计算，然后比较是否和原数值相等。

• 时间复杂度：$O(log(x))$
• 空间复杂度：$O(1)$

class Solution:def isPalindrome(self, x: int) -> bool:n = 0if x < 0:return Falsey = xwhile y > 0:n = n * 10 + y % 10y = y // 10return n == x