力扣面试题 23
题目：
动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如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思路：
使用一个双端链表的结构来表示动物队列。队列包含两种类型的动物：猫和狗。每个动物节点包含其编号和种类信息。收养动物但不指定猫还是狗时，如何判断谁更“老”呢？可以通过比较序号的方式判断。具体函数设计：
1. 数据结构设计 使用了一个双端链表的结构来表示动物队列。队列包含两种类型的动物：猫和狗。每个动物节点包含其编号和种类信息。使用 *head 和 *tail 分别表示队列的头部和尾部指针，便于在队列两端进行操作。需要分别处理猫、狗和任意动物的入队和出队操作。 2. animalShelfCreate 创建队列 初始化一个空的 AnimalShelf 结构体，其中 head 和 tail 都初始化为 NULL，表示队列为空。 3. animalShelfEnqueue 入队操作 根据传入的动物数据（编号和种类），创建一个新的动物节点。如果队列为空（即 *tail == NULL），将新的动物节点作为队列的第一个元素，*head 和 *tail 都指向该节点。如果队列不为空，则根据动物种类（猫或狗）将新节点添加到对应的队列末尾，更新 *tail。 4. animalShelfDequeueAny 任意出队操作 判断队列是否为空。如果队列为空，直接返回 NULL。如果队列非空，返回头部节点（第一个入队的动物）。更新 *head，让它指向下一个动物节点。如果更新后队列为空，还需要将 *tail 置为 NULL。 5. animalShelfDequeueDog 狗出队操作 判断队列是否为空。如果为空，返回 NULL。否则，从队列中寻找最早进入队列的狗并将其出队。更新头部指针 *head，并且如果队列为空，还需要将 *tail 置为 NULL。 6. animalShelfDequeueCat 猫出队操作 判断队列是否为空。如果为空，返回 NULL。否则，从队列中寻找最早进入队列的猫并将其出队。更新头部指针 *head，并且如果队列为空，还需要将 *tail 置为 NULL。 7. animalShelfFree 释放队列 释放队列中所有节点的内存。C代码如下：
typedef struct Animal {
int id;
int type;
struct Animal* next;
} Animal;
typedef struct {
Animal* dogHead;
Animal* catHead;
Animal* dogTail;
Animal* catTail;
} AnimalShelf;
AnimalShelf* animalShelfCreate() {
AnimalShelf* shelf = (AnimalShelf*)malloc(sizeof(AnimalShelf));
shelf->dogHead = NULL;
shelf->catHead = NULL;
shelf->dogTail = NULL;
shelf->catTail = NULL;
return shelf;
}
void enqueueAnimal(Animal** head, Animal** tail, int id, int type) {
Animal* newAnimal = (Animal*)malloc(sizeof(Animal));
newAnimal->id = id;
newAnimal->type = type;
newAnimal->next = NULL;
if (*tail) {
(*tail)->next = newAnimal;
} else {
*head = newAnimal;
}
*tail = newAnimal;
}
Animal* dequeueAnimal(Animal** head, Animal** tail) {
if (!*head) return NULL;
Animal* animal = *head;
*head = (*head)->next;
if (!*head) {
*tail = NULL;
}
return animal;
}
int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize);
int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize);
void animalShelfEnqueue(AnimalShelf* obj, int* animal, int animalSize) {
if (animal[1] == 0) {
enqueueAnimal(&obj->catHead, &obj->catTail, animal[0], animal[1]);
} else if (animal[1] == 1) {
enqueueAnimal(&obj->dogHead, &obj->dogTail, animal[0], animal[1]);
}
}
int* animalShelfDequeueAny(AnimalShelf* obj, int* retSize) {
*retSize = 2;
if (!obj->dogHead && !obj->catHead) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = -1;
result[1] = -1;
return result;
}
if (!obj->dogHead) return animalShelfDequeueCat(obj, retSize);
if (!obj->catHead) return animalShelfDequeueDog(obj, retSize);
if (obj->dogHead->id < obj->catHead->id) {
return animalShelfDequeueDog(obj, retSize);
} else {
return animalShelfDequeueCat(obj, retSize);
}
}
int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize) {
*retSize = 2;
Animal* dog = dequeueAnimal(&obj->dogHead, &obj->dogTail);
if (!dog) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = -1;
result[1] = -1;
return result;
}
int* result = (int*)malloc(2 * sizeof(int));
result[0] = dog->id;
result[1] = dog->type;
free(dog);
return result;
}
int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize) {
*retSize = 2;
Animal* cat = dequeueAnimal(&obj->catHead, &obj->catTail);
if (!cat) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = -1;
result[1] = -1;
return result;
}
int* result = (int*)malloc(2 * sizeof(int));
result[0] = cat->id;
result[1] = cat->type;
free(cat);
return result;
}
void animalShelfFree(AnimalShelf* obj) {
Animal* temp;
while (obj->dogHead) {
temp = obj->dogHead;
obj->dogHead = obj->dogHead->next;
free(temp);
}
while (obj->catHead) {
temp = obj->catHead;
obj->catHead = obj->catHead->next;
free(temp);
}
free(obj);
}
相关知识
力扣面试题 23
正高副高级职称考试宝典内分泌学副主任医师面审答辩面试题陕西省
经典的逻辑面试题
宠物扣具A
25mm雌雄扣厂家
盘扣架=轮扣架？工程人要清楚！
宠物马扣
钥匙扣，狗扣，合金扣，箱包扣，宠物扣，绳带扣，吊牌扣
宠物用带体的磁扣.pdf
宠物扣具的一些常识，宠物锌合金扣具厂家为你解惑
网址: 力扣面试题 23 https://m.mcbbbk.com/newsview629203.html
| 上一篇: 广州有可以领养猫咪的宠物店吗?广 |
下一篇: 宠物领养平台，领养宠物的网站是什 |
