前言
LeetCode中有关
队列
的题目。
1. LeetCode933:最近的请求次数
LeetCode的第933题:
最近的请求次数
。
这个题首先要读懂题|ू・ω・` ),题的意思可以理解为有一个队列,然后计算队列元素在区间
[t-3000,3000]
内的的个数。代码如下:
class RecentCounter:
def __init__(self):
self.queue = []
def ping(self, t):
self.queue.append(t)
while self.queue[0] < t - 3000:
self.queue = self.queue[1:]
return len(self.queue)
运行结果如下:
2. LeetCode641:设计循环双端队列
LeetCode的第641题:
设计循环双端队列
。
这个题主要就是借助Python里面的
collections
库里面的
deque
类来构建双端队列,下面就介绍
deque
类里面几个常用的方法:
方法
|
功能
|
collections.deque(maxlen)
|
初始化一个最大长度为
m
a
x
l
e
n
m
a
x
l
e
n
双端队列,当双端队列已经满时,再插入数据,就会有相应个数的数据从另一端出来
|
append(value)
|
添加
v
a
l
u
e
v
a
l
u
e
到右端
|
appendleft(value)
|
添加
v
a
l
u
e
v
a
l
u
e
到左端
|
pop()
|
移除最右侧的元素
|
popleft()
|
移除最左侧的元素
|
extend(iterable)
|
在队列右侧添加
i
t
e
r
a
b
l
e
i
t
e
r
a
b
l
e
中的元素
|
extendleft(iterable)
|
在队列左侧添加
i
t
e
r
a
b
l
e
i
t
e
r
a
b
l
e
中的元素(
i
t
e
r
a
b
l
e
i
t
e
r
a
b
l
e
参数的顺序将会反过来添加)
|
除此之外还有
clear()
、
copy()
、
count()
、
index()
、
insert()
、
remove()
、
reverse()
,这里就不一一介绍了。
代码如下:
class MyCircularDeque:
def __init__(self, k):
from collections import deque
self.length = k
self.queue = deque(maxlen=self.length)
def insertFront(self, value):
if self.isFull():
return False
else:
self.queue.appendleft(value)
return True
def insertLast(self, value):
if self.isFull():
return False
else:
self.queue.append(value)
return True
def deleteFront(self):
if self.isEmpty():
return False
else:
self.queue.popleft()
return True
def deleteLast(self):
if self.isEmpty():
return False
else:
self.queue.pop()
return True
def getFront(self):
if self.isEmpty():
return -1
else:
return self.queue[0]
def getRear(self):
if self.isEmpty():
return -1
else:
return self.queue[-1]
def isEmpty(self):
if len(self.queue
) == 0:
return True
else:
return False
def isFull(self):
if len(self.queue) == self.length:
return True
else:
return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
运行结果如下:
3. LeetCode622:设计循环队列
LeetCode的第622题:
设计循环队列
。
有关循环队列的操作及代码实现,请参考的我的
这篇博客
,这里不再叙述,代码如下:
class MyCircularQueue:
def __init__(self, k: int):
self.length = k + 1
self.queue = [None] * self.length
self.front = 0
self.rear = 0
def enQueue(self, value):
if self.isFull():
return False
else:
self.queue[self.rear] = value
self.rear = (self.rear + 1) % self.length
return True
def deQueue(self):
if self.isEmpty():
return False
else:
self.front = (self.front + 1) % self.length
return True
def Front(self):
if self.isEmpty():
return -1
else:
return self.queue[self.front]
def Rear(self):
if self.isEmpty():
return -1
else:
return self.queue[self.rear-1]
def isEmpty(self):
if self.front == self.rear:
return True
else:
return False
def isFull(self):
if (self.rear + 1) % self.length == self.front:
return True
else:
return False
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
运行结果如下:
结束语
队列的题貌似不太多(也许是没有找到),就选了这几个常规题先简单练习一下,大致感觉简单的队列就直接用列表,双端队列就直接使用
collections
库里面的
deque
类,其他的暂时还没有想到,嘿嘿。