动物收容所

题目

思路

使用双端队列来实现，具体看代码注释

import collections
class AnimalShelf:
    def __init__(self):
        # 先进先出：队列
        # 出队狗或者猫，先把其他动物用一个数组保存，找到需要的东西，
        # 再把临时数组加到队列上
        # 用双端队列实现
        self.deque = collections.deque()
    def enqueue(self, animal: List[int]) -> None:
        self.deque.append(animal)
    def dequeueAny(self) -> List[int]:
        if self.is_empty():
            return [-1, -1]
        return self.deque.popleft()
    def dequeueDog(self) -> List[int]:
        return self.dequeueClass(class_id=1)
    def dequeueCat(self) -> List[int]:
        return self.dequeueClass(class_id=0)
    def dequeueClass(self, class_id) -> List[int]:
        if self.is_empty():
            return [-1, -1]
        tmp = []
        while self.deque[0][1] != class_id:
            tmp.append(self.deque.popleft())
            if self.is_empty():
                for i in tmp[::-1]:
                    self.deque.appendleft(i)
                return [-1, -1]
        # 找到最老的小狗
        ans = self.deque.popleft()
        # 把tmp返回
        for i in tmp[::-1]:
            self.deque.appendleft(i)
        return ans
    def is_empty(self):
        return not self.deque
# Your AnimalShelf object will be instantiated and called as such:
# obj = AnimalShelf()
# obj.enqueue(animal)
# param_2 = obj.dequeueAny()
# param_3 = obj.dequeueDog()
# param_4 = obj.dequeueCat()