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不会出现溢出问题)
- 思路二
上面的解法虽然通过了,但是存在着一些问题:
- 缺少一些临界条件的判断,如负数肯定不是回文数,末位为0且该数不为0的数肯定也不是回文数
- 最坏的情况下时间复杂度为 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(log10x)
更多推荐
**Leetcode 9 Palidrome Number
发布评论