Python双端队列实现回文检测

 更新时间:2022年01月14日 14:10:59   作者:叶庭云  
双端队列 Deque 是一种有次序的数据集,跟队列相似,其两端可以称作"首" 和 "尾"端。这篇文章将通过双端队列实现回文检测,感兴趣的可以学习一下

一、双端队列

双端队列 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回文检测内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!

相关文章

  • Python环境搭建之OpenCV的步骤方法

    Python环境搭建之OpenCV的步骤方法

    本篇文章主要介绍了Python环境搭建之OpenCV的步骤方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2017-10-10
  • keras 模型参数,模型保存,中间结果输出操作

    keras 模型参数,模型保存,中间结果输出操作

    这篇文章主要介绍了keras 模型参数,模型保存,中间结果输出操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2020-07-07
  • django实现用户登陆功能详解

    django实现用户登陆功能详解

    这篇文章主要介绍了django实现用户登陆功能详解,具有一定借鉴价值,需要的朋友可以参考下。
    2017-12-12
  • 用python实现刷点击率的示例代码

    用python实现刷点击率的示例代码

    今天小编就为大家分享一篇用python实现刷点击率的示例代码,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-02-02
  • 教你学会通过python的matplotlib库绘图

    教你学会通过python的matplotlib库绘图

    今天教大家如何学会通过python的matplotlib库绘图,文中有非常详细的图文解说及代码示例,对正在学习python的小伙伴们很有帮助,需要的朋友可以参考下
    2021-05-05
  • Python Django搭建文件下载服务器的实现

    Python Django搭建文件下载服务器的实现

    这篇文章主要介绍了Python Django搭建文件下载服务器的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2021-05-05
  • Python中方法链的使用方法

    Python中方法链的使用方法

    这篇文章主要为大家详细介绍了Python中方法链的使用方法,方法链(method chaining)是面向对象的编程语言中的一种常见语法,对方法链感兴趣的小伙伴们可以参考一下
    2016-02-02
  • pandas表连接 索引上的合并方法

    pandas表连接 索引上的合并方法

    今天小编就为大家分享一篇pandas表连接 索引上的合并方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2018-06-06
  • Python实战之外星人入侵游戏示例代码

    Python实战之外星人入侵游戏示例代码

    这篇文章主要介绍了利用Python编写的外星人入侵游戏的示例代码,文中的代码讲解详细,对我们学习Python有一定的帮助,感兴趣的可以学习一下
    2022-01-01
  • python 使用递归实现打印一个数字的每一位示例

    python 使用递归实现打印一个数字的每一位示例

    今天小编就为大家分享一篇python 使用递归实现打印一个数字的每一位示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2020-02-02

最新评论