用wordpress做购物网站,龙岩品牌设计,网页设计实验报告书,网站内链建设属于什么内容文章目录 一、题目二、C# 题解 一、题目 动物收容所。有家动物收容所只收容狗与猫#xff0c;且严格遵守“先进先出”的原则。在收养该收容所的动物时#xff0c;收养人只能收养所有动物中“最老”#xff08;由其进入收容所的时间长短而定#xff09;的动物#xff0c;或… 文章目录 一、题目二、C# 题解 一、题目 动物收容所。有家动物收容所只收容狗与猫且严格遵守“先进先出”的原则。在收养该收容所的动物时收养人只能收养所有动物中“最老”由其进入收容所的时间长短而定的动物或者可以挑选猫或狗同时必须收养此类动物中“最老”的。换言之收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构实现各种操作方法比如 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 Queueint[] cat;private Queueint[] dog;public AnimalShelf() {cat new Queueint[]();dog new Queueint[]();}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] 为 catfront[1] 为 dogfront % 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;}
}时间复杂度无。空间复杂度无。
