概述
2019独角兽企业重金招聘Python工程师标准>>> 
有家动物收容所只收容狗与猫，且严格遵守“先进先出”原则。在收养该收容所的动物时，收养人只能收养进入收容所时间最长的动物，或者，挑选猫或狗中收养时间最长的。
请创建适合这个系统的数据结构，实现各种操作方法，比如enqueue，dequeueAny， dequeDog, dequeueCat等，允许使用Java内置的LinkedList数据结构
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
题目分析：
根据先进先出的原则，自然想到了用队列实现，如果只维护一个队列，那么第一种方法实现起来比较简单，只需要取出队头的动物则可以，但是第二种方法就比较复杂，需要访问整个队列来找出第一个被访问的猫或者狗。
因此我们可以选择维护两个队列来实现，一个队列存放放入的狗，一个队列存放放入的猫，对于第二种方法实现起来相当容易，我们只需要根据要选择的猫或者狗从 相应的队列中取出便可以，但是第一种方法需要判断那个两个队列头部的是猫先进入收容所，还是狗先进入，这个时候需要一个标志，所以我们每次把动物放入队列 的时候，同时将一个递增的序号放入队列，这个序号就是一个时间序列，根据这个序号便可以轻松实现第一种方法。
思路：
1、方法一：维护一个队列，dequeueAny实现简单，但是dequeueDog和dequeueDog需要迭代访问整个队列，才能找到第一只该被收养的猫或狗。
2、方法二：
[java] view plain copy
- /**
- * 方法二：为狗和猫各自建一个队列，然后将两者放进名为AnimalQueue的类中，并且存储某种形式的时间戳，来标记每只动物进入队列的时间。调用dequeueAny时，查看狗队列和猫队列的首部，并返回最老的那一只。
- */
- import java.util.*;
- public class AnimalQueue {
- LinkedList<Dog> dogs= new LinkedList<Dog>();
- LinkedList<Cat> cats= new LinkedList<Cat>();
- private int order=0;//时间戳
- public void enqueue(Animal a){
- a.setOrder( order);
- order++;
- if( a instanceof Dog)
- dogs.add((Dog) a);
- else if( a instanceof Cat)
- cats.add((Cat) a);
- }
- public Animal dequeueAny(){
- if( dogs.size()==0)
- return dequeueCat();
- else if( cats.size()==0)
- return dequeueDog();
- Dog dog= dogs.peek(); //not remove
- Cat cat= cats.peek();
- if( dog.isOlderThan( cat))
- return dequeueDog(); //此时需要remove，所以不能只是返回dog
- else
- return dequeueCat();
- }
- public Dog dequeueDog(){
- return dogs.poll(); //remove
- }
- public Cat dequeueCat(){
- return cats.poll();
- }
- }
- class Dog extends Animal{
- public Dog(String n) {
- super( n);
- }
- }
- class Cat extends Animal{
- public Cat(String n) {
- super( n);
- }
- }
- abstract class Animal{
- int order;
- String name;
- public Animal(String n){
- this. name= n;
- }
- public int getOrder() {
- return order;
- }
- public void setOrder( int order) {
- this. order = order;
- }
- public boolean isOlderThan(Animal a){
- return this.getOrder()< a.getOrder();
- }
- }
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。若第一个元素为1，则代表有动物 进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式，若为 1，则指定收养狗，若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。
测试样例：
[[1,1],[1,-1],[2,0],[2,-1]]
返回：[1,-1]
或者
public ArrayList<Integer> asylum(int[][] ope) {
class Animal {
int id, order;
public Animal(int id, int order) {
this.id = id;
this.order = order;
}
}
int order = 0;
LinkedList<Animal> dogs = new LinkedList<>();
LinkedList<Animal> cats = new LinkedList<>();
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < ope.length; i++) {
if (ope[i][0] == 1) {
if (ope[i][1] > 0)
dogs.add(new Animal(ope[i][1], order++));
else if (ope[i][1] < 0)
cats.add(new Animal(ope[i][1], order++));
}
else if (ope[i][0] == 2) {
if (ope[i][1] == 0) {
Animal d = dogs.peek();
Animal c = cats.peek();
boolean flag = false;
if (d != null && c != null) {
if (d.order - c.order < 0)
flag = true;
} else if (d == null && c == null)
continue;
else if (d != null)
flag = true;
if (flag)
list.add(dogs.removeFirst().id);
else
list.add(cats.removeFirst().id);
} else if (ope[i][1] == 1) {
if (dogs.peek() != null)
list.add(dogs.removeFirst().id);
} else if (ope[i][1] == -1) {
if (cats.peek() != null)
list.add(cats.removeFirst().id);
}
}
}
return list;
}
或者：
import java.util.*;
public class CatDogAsylum {
public ArrayList<Integer> asylum(int[][] ope) {
// write code here
ArrayList<Integer> result = new ArrayList<Integer>();
if(null==ope||ope.length<=0)
return result;
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i=0;i<ope.length;i++){
if(ope[i][0]==1){//进入
temp.add(ope[i][1]);
}
if(ope[i][0]==2){//收养
if(ope[i][1]==0&&temp.size()>0)//采用第一种收养方式
result.add(temp.remove(0));
else if(ope[i][1]==-1){//指定收养猫
for(int j=0;j<temp.size();j++){
if(temp.get(j)<0){
result.add(temp.remove(j));
break;
}
}
}
else if(ope[i][1]==1){//指定收养狗
for(int k=0;k<temp.size();k++){
if(temp.get(k)>0){
result.add(temp.remove(k));
break;
}
}
}
}
}
return result;
}
}
转载于:https://my.oschina.net/u/2822116/blog/789495
最后
以上就是开心航空为你收集整理的动物收容所，先进先出的全部内容，希望文章能够帮你解决动物收容所，先进先出所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复