当前位置: 萬仟网 > IT编程>脚本编程>Python > Python双端队列实现回文检测

Python双端队列实现回文检测

2022年01月14日 Python 我要评论
目录一、双端队列二、回文检测补充一、双端队列双端队列 deque 是一种有次序的数据集,跟队列相似,其两端可以称作"首" 和 "尾"端,但 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回文检测内容请搜索萬仟网以前的文章或继续浏览下面的相关文章希望大家以后多多支持萬仟网!

(0)
打赏 微信扫一扫 微信扫一扫

相关文章:

  • Java基于LoadingCache实现本地缓存的示例代码

    Java基于LoadingCache实现本地缓存的示例代码

    目录一、 添加 maven 依赖二、cachebuilder 方法说明三、创建 cacheloader四、工具类五、guava cache数据移除一、 添加 m... [阅读全文]
  • Java实现猜数字小游戏代码

    Java实现猜数字小游戏代码

    目录▲游戏规则:▲实现思路:实验结果:总结▲游戏规则:系统随机生成一个范围0——100的数,用户输入数字,判断该数字是大于,小于,还是等... [阅读全文]
  • Python特效之文字成像方法详解

    Python特效之文字成像方法详解

    目录一、特效预览二、程序原理三、程序源码一、特效预览处理前处理后细节放大后二、程序原理1.输入你想隐藏的文字2.然后写到另一张跟照片同等大小的空白纸张上3.将相... [阅读全文]
  • JavaScript函数柯里化详解

    JavaScript函数柯里化详解

    目录一、简单了解apply和call二、什么是函数柯里化?三、写一个公共的柯里化函数四、创建一个灵活的柯里化函数五、写一个可控制的执行时间的柯里化函数总结一、简... [阅读全文]
  • 关于Java反射给泛型集合赋值问题

    关于Java反射给泛型集合赋值问题

    泛型java泛型简单描述下:比如创建一个list集合,我想在里边只放student对象信息,就需要写成list<student> studentli... [阅读全文]

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

验证码:
Copyright © 2017-2022  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com