【数据结构】队列 Queue

1、leetcode346:数据流中的移动平均值

给定一个整数数据流和一个窗口大小,根据该滑动窗口的大小,计算其所有整数的移动平均值。

示例:
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MovingAverage:

def __init__(self, size: int):
self.queue = []
for _ in range(size):
self.queue.append(0)
self.length = 0
return

def next(self, val: int) -> float:
if self.length < len(self.queue):
self.queue[self.length] = val
self.length += 1
return sum(self.queue)/self.length
else:
self.queue[:-1] = self.queue[1:]
self.queue[-1] = val
return sum(self.queue)/self.length

obj = MovingAverage(3)
print(obj.next(1))
print(obj.next(10))
print(obj.next(5))
print(obj.next(7))

2、leetcode933:最近的请求次数

写一个 RecentCounter 类来计算最近的请求,它只有一个方法:ping(int t),其中 t 代表以毫秒为单位的某个时间,返回从 3000 毫秒前到现在的 ping 数。
任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内,包括当前(指 t 时刻)的 ping。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class RecentCounter:

def __init__(self):
import collections
self.q = collections.deque()

def ping(self, t):
self.q.append(t)
while self.q[0] < t-3000:
self.q.popleft()
return len(self.q)

obj = RecentCounter()
print(obj.ping(1))
print(obj.ping(100))
print(obj.ping(3001))
print(obj.ping(3002))
0%