**Leetcode 9 Palidrome Number

Leetcode 9 Palidrome Number"/>

**Leetcode 9 Palidrome Number

Leetcode 9 Palidrome Number

题目描述

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目解析

• 思路一
  我们知道回文数是正向读和逆向读的结果完全一样的一种特殊数字，那我们完全可以首先将回文数转换为字符串，比较处于对称位置的字符是否相同，如果出现不同，该数不为回文数，如果遍历完整个字符串都没有出现不同的地方，那该数便为回文数。代码如下：

class Solution:def isPalindrome(self, x: int) -> bool:x = str(x)length = len(x)i = 0while i <= length // 2:if x[i] != x[-1 - i]:return Falsei = i + 1return True

这样的方式，在最坏的情况下需要遍历整个字符串，其时间复杂度为 O ( l e n ( x ) ) O(len(x)) O(len(x))
此外，和上面的思路一样，但不转换为字符串，利用%、/提取对应位置的数字，看是否相等，从而判断是否为回文数。
还有一种更简单的方式，反转数字，比较反转前和反转后是否相等，很容易能得到答案。但这样的解法需要额外的空间存储反转后的数字，且时间复杂度显然不如上面的解法，而且需要处理反转后可能出现的溢出问题（虽然python不会出现溢出问题）

• 思路二
  上面的解法虽然通过了，但是存在着一些问题：

1. 缺少一些临界条件的判断，如负数肯定不是回文数，末位为0且该数不为0的数肯定也不是回文数
2. 最坏的情况下时间复杂度为 O ( l e n ( x ) ) O(len(x)) O(len(x))
   参照官方答案的解答，判断是否为回文数，即对折该数，看是否重合，从而判断是否为回文数。此外，加入边界条件的判断

class Solution:def isPalindrome(self, x: int) -> bool:if x < 0 or (x % 10 == 0 and x != 0):return Falserev = 0while (x > rev):rev = rev * 10 + x % 10x = x // 10return (x == rev or x == rev // 10)

时间复杂度为 O ( l o g 10 x ) O(log_{10}x) O(log10​x)