LeetCode 面试题 03.06. 动物收容所

一、题目

  动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如 enqueue、dequeueAny、dequeueDog 和 dequeueCat。允许使用 Java 内置的 LinkedList 数据结构。

  enqueue 方法有一个 animal 参数，animal[0] 代表动物编号，animal[1] 代表动物种类，其中 0 代表猫，1 代表狗。

  dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

  点击此处跳转题目。

示例1:

输入：
[“AnimalShelf”, “enqueue”, “enqueue”, “dequeueCat”, “dequeueDog”, “dequeueAny”]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]

示例2:

输入：
[“AnimalShelf”, “enqueue”, “enqueue”, “enqueue”, “dequeueDog”, “dequeueCat”, “dequeueAny”]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：
[null,null,null,null,[2,1],[0,0],[1,0]]

说明:

• 收纳所的最大容量为20000

二、C# 题解

  使用双队列即可实现，在 dequeueAny 中，需要判断两个队列对首的先后次序。实现如下：

public class AnimalShelf {private Queue<int[]> cat;private Queue<int[]> dog;public AnimalShelf() {cat = new Queue<int[]>();dog = new Queue<int[]>();}public void Enqueue(int[] animal) {if (animal[1] == 0) cat.Enqueue(animal);else dog.Enqueue(animal);}public int[] DequeueAny() {if (cat.Count == 0) return DequeueDog();if (dog.Count == 0) return DequeueCat();int[] c = cat.Peek(), d = dog.Peek();if (c[0] < d[0]) return DequeueCat();else return DequeueDog(); }public int[] DequeueDog() {if (dog.Count == 0) return new int[] {-1, -1};return dog.Dequeue();}public int[] DequeueCat() {if (cat.Count == 0) return new int[] {-1, -1};return cat.Dequeue();}
}/*** Your AnimalShelf object will be instantiated and called as such:* AnimalShelf obj = new AnimalShelf();* obj.Enqueue(animal);* int[] param_2 = obj.DequeueAny();* int[] param_3 = obj.DequeueDog();* int[] param_4 = obj.DequeueCat();*/

• 时间复杂度：无。
• 空间复杂度：无。

  这样实现当然非常简单。因此我手搓了一个队列，用于存储 cat 和 dog，每次出队列时，指针依次寻找对应的动物，将其弹出后，其余的动物依次替补空位。这样的方法当然不够好，不仅空间复杂度没有减少，时间复杂度还增加了。唯一的好处就是：内部存储的结构真的是一个队列，很接近真实情况哈哈！

public class AnimalShelf {private int[][] q;   // 队列private int[] front; // 队首指针，front[0] 为 cat，front[1] 为 dog，front % Max 指向 q 中的位置private int latter;  // 队尾指针，latter % Max 指向 q 中的位置private const int MAX = 20001;public AnimalShelf() {q = new int[MAX][];front = new int[] {0, 0};latter = 0;}public void Enqueue(int[] animal) {q[latter % MAX] = animal;int kind = animal[1];          // 获取动物种类if (front[1 - kind] == latter) // 另一种动物如果为空，则队首指针一起后移front[1 - kind]++; latter++;}public int[] DequeueAny() {if (front[0] == latter && front[1] == latter) return new int[] {-1, -1};if (front[0] < front[1]) return DequeueCat(); // cat 在前，弹出 catelse return DequeueDog();                     // 否则，弹出 dog}public int[] DequeueDog() {if (front[1] == latter) return new int[] {-1, -1}; // 队列空，则直接返回int[] dog = q[front[1] % MAX];                     // 取出队首元素// 前方 cat 后移int i;for (i = front[1]; i > front[0]; i--) q[i % MAX] = q[(i - 1) % MAX];q[i % MAX] = null; // 队首置空if (front[0] != latter && q[front[0] % MAX] == null) front[0]++; // cat 指针后移// 重新定位 dog 指针do {front[1]++;} while (front[1] != latter && q[front[1] % MAX][1] != 1);return dog;}public int[] DequeueCat() {if (front[0] == latter) return new int[] {-1, -1};int[] cat = q[front[0] % MAX];int i;for (i = front[0]; i > front[1]; i--) q[i % MAX] = q[(i - 1) % MAX];q[i % MAX] = null;if (front[1] != latter && q[front[1] % MAX] == null) front[1]++;do {front[0]++;} while (front[0] != latter && q[front[0] % MAX][1] != 0);return cat;}
}

• 时间复杂度：无。
• 空间复杂度：无。