LeetCode 面试题 03.06. 动物收容所

文章目录

一、题目

1、题目描述2、基础框架3、原题链接二、解题报告

1、思路分析2、时间复杂度3、代码详解

1）队列的增删改查2）源码三、本题小知识四、加群须知

一、题目 1、题目描述

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的linkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
样例输入： ["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"] [[], [[0, 0]], [[1, 0]], [], [], []]
样例输出： [null,null,null,[0,0],[-1,-1],[1,0]]

2、基础框架

C语言版本给出的基础框架代码如下：

typedef struct {

} AnimalShelf;

AnimalShelf* animalShelfCreate() {
}

void animalShelfEnqueue(AnimalShelf* obj, int* animal, int animalSize) {
}

int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize) {
}

int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize) {
}

int* animalShelfDequeueAny(AnimalShelf* obj, int* retSize) {
}

void animalShelfFree(AnimalShelf* obj) {
    free(obj);
}

3、原题链接

面试题 03.06. 动物收容所

二、解题报告 1、思路分析

( 1 ) (1) (1) 对于这个题目，其实就是对于 FIFO 队列的基础操作，所以，手写一个队列是很有必要滴。文中有猫和狗两种队列，而出队的时候，如果没有指定猫和狗，则需要选择入队时间更早的进行出队，所以入队的时候需要加上时间参数。
( 2 ) (2) (2) 所以，首先，我们需要实现一个队列的增删改查。
( 3 ) (3) (3) 然后，对于猫和狗的情况，分别进行出队操作。
( 4 ) (4) (4) 对于DequeueAny这种情况，需要判断两个队列的空与否，四种情况：都为空、猫为空、狗为空、都不为空。
( 5 ) (5) (5) 对于都不为空的情况，需要比较两个队列的队首的时间，选择小的那个进行Dequeue操作。

2、时间复杂度

每一步操作都是 O ( 1 ) O(1) O(1)。

3、代码详解 1）队列的增删改查

#define CAT 0
#define DOG 1

typedef struct {
    int front, rear;
    int val[ 20010 ];
    int time[ 20010 ];
}Queue;

// 队列清空操作
void ClearQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 队列入队操作
void Enqueue(Queue *q, int val, int time) {
    q->val[ q->rear ] = val;
    q->time[ q->rear ] = time;
    ++q->rear;
}

// 队列的判空操作
bool IsQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

// 队列的出队操作
int PopQueue(Queue *q) {
    return q->val[ q->front++ ];
}

// 获取队列头元素的时间
int GetQueueFrontTime(Queue *q) {
    return q->time[ q->front ];
}

2）源码

typedef struct {
    Queue q[2];
    int timeId;
} AnimalShelf;


AnimalShelf* animalShelfCreate() {
    AnimalShelf *obj = (AnimalShelf *)malloc( sizeof(AnimalShelf) );
    ClearQueue( &obj->q[CAT] );
    ClearQueue( &obj->q[DOG] );
    obj->timeId = 0;
    return obj;
}

void animalShelfEnqueue(AnimalShelf* obj, int* animal, int animalSize) {
    Enqueue(&obj->q[ animal[1] ], animal[0], ++obj->timeId);
}

int* animalShelfDequeueDog(AnimalShelf* obj, int* retSize) {
    int *ret = (int *)malloc( sizeof(int) * 2 );
    *retSize = 2;
    if(IsQueueEmpty( &obj->q[DOG] )) {
        ret[0] = ret[1] = -1;
    }else {
        ret[0] = PopQueue( &obj->q[DOG] );
        ret[1] = DOG;
    }
    return ret;
}

int* animalShelfDequeueCat(AnimalShelf* obj, int* retSize) {
    int *ret = (int *)malloc( sizeof(int) * 2 );
    *retSize = 2;
    if(IsQueueEmpty( &obj->q[CAT] )) {
        ret[0] = ret[1] = -1;
    }else {
        ret[0] = PopQueue( &obj->q[CAT] );
        ret[1] = CAT;
    }
    return ret;
}


int* animalShelfDequeueAny(AnimalShelf* obj, int* retSize) {
    int *ret = (int *)malloc( sizeof(int) * 2 );
    *retSize = 2;
    if( IsQueueEmpty( &obj->q[CAT] ) && IsQueueEmpty( &obj->q[DOG] ) ) {
        ret[0] = ret[1] = -1;
    }else if(IsQueueEmpty( &obj->q[CAT] )) {
        return animalShelfDequeueDog(obj, retSize);
    }else if(IsQueueEmpty( &obj->q[DOG] )){
        return animalShelfDequeueCat(obj, retSize);
    }else {
        if(GetQueueFrontTime(&obj->q[CAT]) < GetQueueFrontTime(&obj->q[DOG])) {
            return animalShelfDequeueCat(obj, retSize);
        }else {
            return animalShelfDequeueDog(obj, retSize);
        }
    }
    return ret;
}



void animalShelfFree(AnimalShelf* obj) {
    free(obj);
}

三、本题小知识

任何问题，我们都需要考虑极端情况，最坏情况的数据才是这个问题的真正时间复杂度。

四、加群须知

相信看我文章的大多数都是「大学生」，能上大学的都是「精英」，那么我们自然要「精益求精」，如果你还是「大一」，那么太好了，你拥有大把时间，当然你可以选择「刷剧」，然而，「学好算法」，三年后的你自然「不能同日而语」。
那么这里，我整理了「几十个基础算法」的分类，点击开启：

《算法入门指引》
如果链接被屏蔽，或者有权限问题，可以私聊作者解决。

大致题集一览：

为了让这件事情变得有趣，以及「照顾初学者」，目前题目只开放最简单的算法「枚举系列」（包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有一半成员刷完「枚举系列」的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「夜深人静写算法」专家团的一员。
不要小看这个专家团，三年之后，你将会是别人望尘莫及的存在。如果要加入，可以联系我，考虑到大家都是学生，没有「主要经济来源」，在你成为神的路上，「不会索取任何」。
联系作者，或者扫作者主页二维码加群，加入刷题行列吧

让天下没有难学的算法
C语言免费动漫教程，和我一起打卡！ 《光天化日学C语言》
让你养成九天持续刷题的习惯 《九日集训》
入门级C语言真题汇总李《C语言入门100例》李
组团学习，抱团生长 《算法零基础100讲》
几张动图学会一种数据结构 《画解数据结构》
竞赛选手金典图文教程 《夜深人静写算法》

LeetCode 面试题 03.06. 动物收容所

Java相关栏目本月热门文章