Python双端队列实现回文检测

目录

• 一、双端队列
• 二、回文检测
• 补充

一、双端队列

双端队列 Deque 是一种有次序的数据集，跟队列相似，其两端可以称作"首" 和 "尾"端，但 Deque 中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。某种意义上说，双端队列集成了栈和队列的能力。

但双端队列并不具有内在的 LIFO 或者 FIFO 特性，如果用双端队列来模拟栈或队列，需要由使用者自行维护操作的一致性。

用 Python 实现抽象数据类型Deque，Deque定义的操作如下：

• Deque()：创建一个空双端队列；
• add_front(item)：将 item 加入队首；
• add_tail(item)：将 item 加入队尾；
• remove_front()：从队首移除数据项，返回值为移除的数据项；
• remove_tail()：从队尾移除数据项，返回值为移除的数据项；
• is_empty()：返回 Deque 是否为空；
• get_size()：返回 Deque 中包含数据项的个数。

定义双端队列，代码实现如下：

class Deque:
    def __init__(self):   # 创建空的双端队列
        self.items = []

    def is_empty(self):   # 判断双端队列是否为空
        return self.items == []

    def add_front(self, item):   # 从队首加入元素 
        self.items.append(item)

    def add_tail(self, item):    # 从队尾加入元素 
        self.items.insert(0, item)

    def remove_front(self):      # 从队首删除元素 
        if self.is_empty():
            raise Exception('Queue is empty')
        return self.items.pop()

    def remove_tail(self):       # 从队尾删除元素 
        if self.is_empty():
            raise Exception('Queue is empty')
        return self.items.pop(0)

    def get_size(self):          # 获取双端队列元素数量
        return len(self.items)

操作复杂度：add_front / remove_front，O(1)；add_tail / remove_tail，O(n)。

二、回文检测

“回文词” 指正读和反读都一样的词，如radar、bob、toot；中文：“上海自来水来自海上”，“山东落花生花落东山”。

用双端队列很容易解决 “回文词” 问题，先将需要判定的词从队尾加入Deque，再从两端同时移除字符判定是否相同，直到 Deque 中剩下 0 个或 1 个字符。

算法实现如下：

def palindrome_check(string):   # 回文检测
    str_deque = Deque()
    for item in string:
        str_deque.add_front(item)
        
    check_flag = True
    while str_deque.get_size() > 1 and check_flag:
        left = str_deque.remove_front()   # 队尾移除
        right = str_deque.remove_tail()   # 队首移除
        if left != right:   # 只要有一次不相等   不是回文
            check_flag = False
    # 判断完一遍   check_flag为True  是回文
    return check_flag

print(palindrome_check("radar"))
print(palindrome_check("abcbac"))
print(palindrome_check("上海自来水来自海上"))

补充

Python还可以通过双游标判断字符串是否是回文串

从字符串s两端指定两个游标low，high

如果low游标指向了 非字母和数字（即空格和符号）,那么low游标往后移一位；

如果high游标指向了 非字母和数字（即空格和符号）,那么high游标往前移一位；

直至low和high都指向了数字或字母，此时进行比较，是否相同。

如果比较的结果是True，则low往后移一位，high往前移一位

如果比较的结果是False，则直接返回False

重复上述判断，直至low和high重合，此时表示完成了字符串s内前后元素的一一对比判断，返回True即可。

代码如下

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    low = 0
    high = len(s) - 1
    #在字符串为空或只有一个字符时，返回True
    if len(s) <= 1:
      return True
    # 设定low和high对比的条件
    while low < high:
     # 如果不是字母或数字，low往后移一位【low < high为必须条件，不然会造成索引越界】
      while not s[low].isalnum() and low < high:
        low += 1
      # 如果不是字母或数字，high往前移一位
      while not s[high].isalnum() and low < high:
        high -= 1
       # 判断：如果相同，继续下一次对比；如果不相同，直接返回False
      if s[low].lower() == s[high].lower():
        low += 1
        high -= 1
      else:
        return False
    # low和high重合，即退出循环，表示前后都是一一对应的，返回True
   return True

到此这篇关于Python双端队列实现回文检测的文章就介绍到这了,更多相关Python回文检测内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！