python回纹判断_判断回文字符串、回文链表、回文数（python实现）

所谓回文字符串&＃xff0c;就是正读和反读都一样的字符串&＃xff0c;比如“level”或者“noon”等等就是回文串。即是对称结构

判断回文字符串

方法一&＃xff1a;

def is_palindrome(s):

return True if s &＃61;&＃61; s[::-1] else False

方法二&＃xff1a;

def is_palindrome(s):

length &＃61; len(s)

if not length: # 空字符串

return True

mid_index &＃61; length // 2 # 如果s长度为奇数则是中点&＃xff0c;偶数则是后面那个中点

index &＃61; 0

status &＃61; True

while index

if s[index] &＃61;&＃61; s[length - 1 - index]:

index &＃43;&＃61; 1

else:

status &＃61; False

break

return status

判断回文链表

思路

我们需要找到链表中点(快慢指针法)

将链表后半段倒置逆序排序

将前半段和后半段遍历比较&＃xff0c;判断是否为回文链表&＃xff0c;偶数情况&＃xff0c;使用偶数定位中点策略&＃xff0c;要确定是返回上中位数或下中位数

注意事项&＃xff1a;

快慢指针定位中点时要区分奇偶情况&＃xff0c;奇数情况&＃xff0c;中点位置不需要矫正&＃xff0c;偶数情况&＃xff0c;使用偶数定位中点策略&＃xff0c;要确定是返回上中位数或下中位数

如果是返回上中位数&＃xff0c;后半部分串头取next&＃xff0c;如果是返回下中位数&＃xff0c;后半部分串头既是当前节点位置&＃xff0c;但前半部分串尾要删除掉当前节点

代码

class Solution(object):

def is_palindrome(self, head: ListNode) -> bool:

if head is None: # 空

return False

if head.next is None: # 1个节点

return True

slow &＃61; fast &＃61; head

# 1. 定中点

while fast and fast.next:

slow &＃61; slow.next

fast &＃61; fast.next.next

# 快慢指针定位中点&＃xff0c;此时fast已到达链尾&＃xff0c;如果长度为奇数&＃xff0c;则slow到达中心点&＃xff0c;长度为偶数&＃xff0c;则slow到达下中位点

# 2. 后半段倒置

pre &＃61; None # 倒置后的最后一个节点必为None,以此确定第三步遍历时的终点

cur &＃61; slow # 当前要倒置的第一个节点

nxt &＃61; slow.next # 当前要倒置的节点的下一个节点

while nxt: # 只要没有到达原链表的终点就一直进行倒置

cur.next &＃61; pre # 将当前节点的下一个节点指向"前"一个节点&＃xff0c;进行倒置

# 相邻节点倒置完成后&＃xff0c;向后整体偏移1个单位

pre &＃61; cur

cur &＃61; nxt

nxt &＃61; cur.next

# 当前cur是最后一个节点&＃xff0c;需要和它前面的节点进行最后一次倒置&＃xff0c;来完成整个后半段倒置

cur.next &＃61; pre

# 3. cur就是倒置完成后的后半段的头节点,同时遍历cur和head&＃xff0c;如果遍历完cur未出现不同的节点&＃xff0c;则为回文链表

while cur.next:

if cur.val !&＃61; head.val:

return False

cur &＃61; cur.next

head &＃61; head.next

# 此时cur为后半段的最后一个节点&＃xff0c;还需要判断此时的cur和head的值是否相同

return cur.val &＃61;&＃61; head.val

测试

# head &＃61;None

head &＃61; ListNode(1)

head.next &＃61; ListNode(2)

head.next.next &＃61; ListNode(1)

print(Solution().is_palindrome(head))

判断回文数

思路

映入脑海的第一个想法是将数字转换为字符串&＃xff0c;并检查字符串是否为回文。但是&＃xff0c;这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转&＃xff0c;然后将反转后的数字与原始数字进行比较&＃xff0c;如果它们是相同的&＃xff0c;那么这个数字就是回文。 但是&＃xff0c;如果反转后的数字大于 int.MAX&＃xff0c;我们将遇到整数溢出问题。

按照第二个想法&＃xff0c;为了避免数字反转可能导致的溢出问题&＃xff0c;为什么不考虑只反转int 数字的一半&＃xff1f;毕竟&＃xff0c;如果该数字是回文&＃xff0c;其后半部分反转后应该与原始数字的前半部分相同。

例如&＃xff0c;输入 1221&＃xff0c;我们可以将数字“1221”的后半部分从“21”反转为“12”&＃xff0c;并将其与前半部分“12”进行比较&＃xff0c;因为二者相同&＃xff0c;我们得知数字 1221 是回文。

让我们看看如何将这个想法转化为一个算法。

算法

首先&＃xff0c;我们应该处理一些临界情况。所有负数都不可能是回文&＃xff0c;例如&＃xff1a;-123 不是回文&＃xff0c;因为 - 不等于 3。所以我们可以对所有负数返回 false。

现在&＃xff0c;让我们来考虑如何反转后半部分的数字。 对于数字 1221&＃xff0c;如果执行 1221 % 10&＃xff0c;我们将得到最后一位数字 1&＃xff0c;要得到倒数第二位数字&＃xff0c;我们可以先通过除以 10 把最后一位数字从 1221 中移除&＃xff0c;1221 / 10 &＃61; 122&＃xff0c;再求出上一步结果除以10的余数&＃xff0c;122 % 10 &＃61; 2&＃xff0c;就可以得到倒数第二位数字。如果我们把最后一位数字乘以10&＃xff0c;再加上倒数第二位数字&＃xff0c;1 * 10 &＃43; 2 &＃61; 12&＃xff0c;就得到了我们想要的反转后的数字。 如果继续这个过程&＃xff0c;我们将得到更多位数的反转数字。

现在的问题是&＃xff0c;我们如何知道反转数字的位数已经达到原始数字位数的一半&＃xff1f;

我们将原始数字除以 10&＃xff0c;然后给反转后的数字乘上 10&＃xff0c;所以&＃xff0c;当原始数字小于反转后的数字时&＃xff0c;就意味着我们已经处理了一半位数的数字。

代码

class Solution(object):

def is_palindrome(self, num: int) -> bool:

# 当 x <0 时&＃xff0c;x 不是回文数

# 如果数字的最后一位是 0&＃xff0c;为了使该数字为回文&＃xff0c;则其第一位数字也应该是 0

# 只有 0 满足这一属性

if num <0 or (num % 10 &＃61;&＃61; 0 and num !&＃61; 0):

return False

reverted_num &＃61; 0

while num > reverted_num:

reverted_num &＃61; reverted_num * 10 &＃43; num % 10

num /&＃61; 10

# 当数字长度为奇数时&＃xff0c;我们可以通过 revertedNumber / 10 去除处于中位的数字。

# 例如&＃xff0c;当输入为12321时&＃xff0c;在 while 循环的末尾我们可以得到 x &＃61; 12&＃xff0c;revertedNumber &＃61; 123&＃xff0c;

# 由于处于中位的数字不影响回文(它总是与自己相等)&＃xff0c;所以我们可以简单地将其去除。

return num &＃61;&＃61; reverted_num or num &＃61;&＃61; reverted_num / 10

# 测试

print(Solution().is_palindrome(0))

print(Solution().is_palindrome(10))

print(Solution().is_palindrome(101))