1. 列表的定义
先进先出（FIFO）
2. 用法
类代码如下：
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def pop(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
3. 算法运用
① 约瑟夫环
剑指offer62
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
# num为传递的次数，每隔一个人就是传递1次
class Solution:
def lastRemaining(self, n: int, num = 2) -> int:
lst = Queue()
for i in range(n):
lst.enqueue(i)
while lst.size() >1:
for i in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
return lst.dequeue()
先按头消去，每隔一个消去；再从第二个每隔一个消去
【1,2,3,4,5,6】→【2,4,6】→【2,6】→【6】
这种方法代码如下：
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
# num为传递的次数，每隔一个人就是传递1次
class Solution:
def lastRemaining(self, n: int, num = 1) -> int:
lst = Queue()
flag = 0
for i in range(1, n+1):
lst.enqueue(i)
mark = lst.size() % 2
while lst.size() // 2 > 0:
if flag == 0:
lst.dequeue()
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 1
if mark == 0:
lst.enqueue(lst.dequeue())
else:
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 0
if mark == 0:
lst.enqueue(lst.dequeue())
return lst.dequeue()
LeetCode 390. 消除游戏
#采用队列和栈的思想，不过虽然超时，但是是正确的。
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def is_empty(self):
return self.items == []
# num为传递的次数，每隔一个人就是传递1次
class Solution:
def lastRemaining(self, n: int, num = 1) -> int:
lst = Queue()
flag = 0
for i in range(1, n+1):
lst.enqueue(i)
while lst.size() // 2 > 0:
mark = lst.size() % 2
if flag == 0:
lst.dequeue()
for i in range(lst.size()//2):
for j in range(num):
lst.enqueue(lst.dequeue())
lst.dequeue()
flag = 1
if mark == 0:
lst.enqueue(lst.dequeue())
else:
lst.items.pop(0)
for i in range(lst.size()//2):
for j in range(num):
lst.items.append(lst.items.pop(0))
lst.items.pop(0)
flag = 0
if mark == 0:
lst.items.append(lst.items.pop(0))
return lst.dequeue()
4 双向队列
两边可以加东西与减东西
image.png
python有双向队列的库，可以直接导入：
from collections import deque
image.png
题目：
- LeetCode 239：双向队列
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
from collections import deque
queue = deque()
for i in range(len(nums)):
if queue and queue[0] < i-k+1:
queue.popleft()
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
if i >= k-1:
res.append(nums[queue[0]])
return res
- Leetcode 9. Palindrome Number
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
if x == 0:
return True
res = deque()
for i in str(x):
res.append(i)
mark = True
while len(res) > 1 and mark is True:
if res.pop() != res.popleft():
mark = False
return mark
