LeetCode 009 回文数

---

Author： Labyrinthine Leo   Init_time： 2021.01.13

---

Index Words： LeetCode 009

---

公众号：Leo的博客城堡

---

题目

• 回文数
• 题号：009
• 难度：简单
• https://leetcode-cn.com/problems/palindrome-number/

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121
输出: true

示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:

你能不将整数转为字符串来解决这个问题吗？

Python实现

1、按位取值比较

思路：将数值按位提取添加到列表中，然后使用双指针首尾遍历列表，进行判断是否相同即可判断回文与否。

时间复杂度：O(n)

空间复杂度：O(n)

• 状态：通过
• 执行用时: 76 ms, 在所有 python3 提交中击败了 66% 的用户
• 内存消耗: 14.7 MB, 在所有 python3 提交中击败了 26.92% 的用户

# coding  : utf-8
# fun     : Leetcode 009 回文数
# @Author : Labyrinthine Leo
# @Time   : 2021.01.13

class Solution:
    def isPalindrome(self, x: int) -> bool:
    	if x < 0:
    		return False
 
    	reverse_list = [] # 将数值各位转为列表存储
    	while x > 0:
    		reverse_list.append(x%10)
    		x //=10
    	# print(reverse_list)
    	l, r = 0, len(reverse_list)-1
    	while l < r: # 首尾双指针比较
    		if reverse_list[l] != reverse_list[r]:
    			return False
    		l += 1
    		r -= 1
    	return True

# 测试样例
x = 121
s = Solution()
print(s.isPalindrome(x))

2、转为字符串对比

思路：同上，只是直接转为字符串进行首尾对称比较，更加方便。

• 状态：通过
• 执行用时: 64 ms, 在所有 python3 提交中击败了 92.83% 的用户
• 内存消耗: 15 MB, 在所有 python3 提交中击败了 5.42% 的用户

# 字符串求解
class Solution:
    def isPalindrome(self, x: int) -> bool:
    	s = str(x)
    	l = len(s)
    	h = l // 2
    	return s[:h] == s[-1:-h-1:-1] # 顺序i+逆序j = -1, 0+-1=-1

# 测试样例
x = -121
s = Solution()
print(s.isPalindrome(x))

---

tips

• 对于字符串首尾对称判断：s[:h] == s[-1:-h-1:-1](h为字符串中间位置索引)

---