leetcode刷题-动物收容所

leetcode刷题-动物收容所

题目描述

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

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

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

解题思路

  • 可以用一个双链表保存收养动物信息,由于需要遵循先进先出的原则,每次收养时都通过尾插法将动物结点保存到双链表中。

  • 收养任意动物,由于采用尾插法,那么最老的动物肯定位于双链表的头结点,只要获取头结点对应的动物数组,然后删除头结点即可。

  • 收养,由于采用尾插法,那么最老的狗(猫)肯定越靠近头结点,只需从头开始遍历双链表,如果找到了狗(猫)对应的结点,返回该结点的动物数组,同时删除该结点。

具体代码

LinkedList 为 java 自带模块,底层基于双链表实现。

import java.util.LinkedList;

class AnimalShelf {
    // 定义一个结点值为数组的双链表
    private LinkedList<int[]> linkedList;

    public AnimalShelf() {
        this.linkedList = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        // 先进先出,将 animal 插入到双链表尾部
        this.linkedList.add(animal);
    }

    public int[] dequeueAny() {
        // 双链表为空
        if (this.linkedList.isEmpty()) {
            return new int[]{-1, -1};
        }
        // 非空,返回头结点的值并删除
        return this.linkedList.removeFirst();
    }

    public int[] dequeueDog() {
        int[] animal = {-1, -1};
        for (int i = 0; i < this.linkedList.size(); i++) {
            // 找到狗对应结点,返回结点值,并删除结点,结束循环
            if (this.linkedList.get(i)[1] == 1) {
                animal = this.linkedList.get(i);
                this.linkedList.remove(i);
                break;
            }
        }
        // 未找到,返回 [-1, -1]
        return animal;
    }

    public int[] dequeueCat() {
        int[] animal = {-1, -1};
        for (int i = 0; i < this.linkedList.size(); i++) {
            // 找到猫对应结点,返回结点值,并删除结点,结束循环
            if (this.linkedList.get(i)[1] == 0) {
                animal = this.linkedList.get(i);
                this.linkedList.remove(i);
                break;
            }
        }
        // 未找到,返回 [-1, -1]
        return animal;
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.cangmangai.cn/archives/animal-shelter-lcci

Buy me a cup of coffee ☕.