题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个路由器类的框架，需要实现添加包、弹出包，查找符合条件的包三个方法。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
class Router:

    def __init__(self, memoryLimit: int):
        self.max_len = memoryLimit
        self.packs = deque()
        self.packSet = set()
        self.dest_to_timestamp = defaultdict(deque)


    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        pack = (source, destination, timestamp)
        if pack in self.packSet:
            return False
        if len(self.packs) >= self.max_len:
            self.forwardPacket()
        self.packSet.add(pack)
        self.packs.append([source, destination, timestamp])
        self.dest_to_timestamp[destination].append(timestamp)
        return True

    def forwardPacket(self) -> List[int]:
        if self.packs:
            res = self.packs.popleft()
            self.dest_to_timestamp[res[1]].popleft()
            self.packSet.remove(tuple(res))
        else:
            res = []
        return res

    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        q = self.dest_to_timestamp[destination]
        l = bisect_left(q, startTime)
        r = bisect_right(q, endTime)
        return r - l

# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)