python使用双端队列实现回文数问题
时间: 2024-01-31 08:02:03 浏览: 28
双端队列是一种数据结构,可以在队列两端进行插入和删除操作。我们可以使用双端队列来判断一个字符串是否为回文数。
回文数是指正着读和倒着读都一样的数。例如,121、1221都是回文数,而123、12321不是回文数。
算法步骤:
1. 将字符串转换为双端队列;
2. 从队列两端依次取出字符进行比较,如果不相等则不是回文数,否则继续比较直到队列为空;
3. 如果队列为空,则为回文数。
Python代码实现:
```python
from collections import deque
def is_palindrome(s):
# 将字符串转换为双端队列
dq = deque(s)
while len(dq) > 1:
# 从队列两端依次取出字符进行比较
if dq.popleft() != dq.pop():
return False
return True
# 测试
print(is_palindrome('121')) # True
print(is_palindrome('1221')) # True
print(is_palindrome('123')) # False
print(is_palindrome('12321')) # True
```
在上面的代码中,我们使用了Python标准库collections中的deque类来创建双端队列。首先将字符串s转换为双端队列dq,然后从队列两端依次取出字符进行比较,如果不相等则返回False,如果队列为空则返回True。