七.Deque的应用案例-回文检查
2024-09-06 14:50:30
- 回文检测:设计程序,检测一个字符串是否为回文。
- 回文:回文是一个字符串,读取首尾相同的字符,例如,radar toot madam
。
- 分析:该问题的解决方案将使用 deque 来存储字符串的字符。我们从左到右处理字符串,并将每个字符添加到 deque 的尾部。在这一点上,deque 像一个普通的队列。然而,我们现在可以利用 deque 的双重功能。 deque 的首部保存字符串的第一个字符,deque 的尾部保存最后一个字符。我们可以直接删除并比较首尾字符,只有当它们匹配时才继续。如果可以持续匹配首尾字符,我们最终要么用完字符,要么留出大小为 1 的deque,取决于原始字符串的长度是偶数还是奇数。在任一情况下,字符串都是回文。
class Dequeue():
def __init__(self):
self.items = []
def addFont(self,item):
self.items.append(item)
def addRear(self,item):
self.items.insert(0,item)
def isEmpty(self):
return self.items == []
def removeFont(self):
if self.isEmpty():
return None
else:
return self.items.pop(0) def removeRear(self):
if self.isEmpty():
return None
else:
return self.items.pop()
def size(self):
return len(self.items)
方法1
def isHuiWei(s):
#将字符添加到双端队列中
q = Dequeue()
#表示字符串是否为回文
for ch in s:
q.addFont(ch) while q.size() > 1:
first = q.removeFont()
last = q.removeRear()
if first != last:
return False
return True
print( isHuiWei('aba'))
True
方法2:
def palchecker(aString):
chardeque = Deque() for ch in aString:
chardeque.addRear(ch) stillEqual = True while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False return stillEqual print(palchecker("lsdkjfskf"))
print(palchecker("radar"))
最新文章
- MySQL5.5绿色版1067
- Practical JAVA(三)关于final
- JS中iframe相关的window.self,window.parent,window.top
- C++/Php/Python/Shell 程序按行读取文件或者控制台
- SPOJ 057 Supernumbers in a permutation
- 怎么保存退出vi编辑
- [Webpack 2] Intro to the Production Webpack Course
- 基于控制权限和登录验证跳转的django登录界面的实现
- Java 并发基础——线程安全性
- vuex概念详解
- 最新sublime text 3 注册码license分享(亲测有效)
- Linux 安装erlang
- (zhuan) 一些RL的文献(及笔记)
- Linux MySQL 安装、远程访问和密码重置
- iOS使用webView加载HTML网页链接简单展示
- Android ActionBar 使用详解
- iOS微信打开App
- js工具库简单介绍
- How to install local .deb packages
- 从内存中直接运行PE程序