Python双端队列怎么实现回文检测
Python双端队列怎么实现回文检测
本文小编为大家详细介绍“Python双端队列怎么实现回文检测”，内容详细，步骤清晰，细节处理妥当，希望这篇“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 中包含数据项的个数。
定义双端队列，代码实现如下：
classDeque:def__init__(self):#创建空的双端队列self.items=[]defis_empty(self):#判断双端队列是否为空returnself.items==[]defadd_front(self,item):#从队首加入元素self.items.append(item)defadd_tail(self,item):#从队尾加入元素self.items.insert(0,item)defremove_front(self):#从队首删除元素ifself.is_empty():raiseException('Queueisempty')returnself.items.pop()defremove_tail(self):#从队尾删除元素ifself.is_empty():raiseException('Queueisempty')returnself.items.pop(0)defget_size(self):#获取双端队列元素数量returnlen(self.items)
操作复杂度：add_front / remove_front，O(1)；add_tail / remove_tail，O(n)。
二、回文检测
“回文词” 指正读和反读都一样的词，如radar、bob、toot；中文：“上海自来水来自海上”，“山东落花生花落东山”。
用双端队列很容易解决 “回文词” 问题，先将需要判定的词从队尾加入Deque，再从两端同时移除字符判定是否相同，直到 Deque 中剩下 0 个或 1 个字符。
算法实现如下：
defpalindrome_check(string):#回文检测str_deque=Deque()foriteminstring:str_deque.add_front(item)check_flag=Truewhilestr_deque.get_size()>1andcheck_flag:left=str_deque.remove_front()#队尾移除right=str_deque.remove_tail()#队首移除ifleft!=right:#只要有一次不相等不是回文check_flag=False#判断完一遍check_flag为True是回文returncheck_flagprint(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即可。
代码如下
classSolution(object):defisPalindrome(self,s):""":types:str:rtype:bool"""low=0high=len(s)-1#在字符串为空或只有一个字符时，返回Trueiflen(s)<=1:returnTrue#设定low和high对比的条件whilelow<high:#如果不是字母或数字，low往后移一位【low<high为必须条件，不然会造成索引越界】whilenots[low].isalnum()andlow<high:low+=1#如果不是字母或数字，high往前移一位whilenots[high].isalnum()andlow<high:high-=1#判断：如果相同，继续下一次对比；如果不相同，直接返回Falseifs[low].lower()==s[high].lower():low+=1high-=1else:returnFalse#low和high重合，即退出循环，表示前后都是一一对应的，返回TruereturnTrue
读到这里，这篇“Python双端队列怎么实现回文检测”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注恰卡编程网行业资讯频道。
