题目源自CC150例3-7,原题描述有家动物收容所只收留猫和狗,但有特殊的领养规则
* 1.直接收养动物中最先进所的
* 2.指定选择收养类型,收养猫或狗中最先进所的
*
* 给定一个操作序列int[][2] ope代表所有事件
* 第一个数为1,代表动物进所,第二个数为动物编号,正数代表狗,负数代表猫
* 第一个数为2,代表收养
* (1)第二个数为0,采取第一种收养方式
* (2)第二个数为1,指定收养狗
* (3)第二个数为-1,指定收养猫
* 按顺序返回收养序列--不合法操作自动忽略
* 样例:进狗,进猫,出最早的(任意动物),出猫
* {{1,1}, {1,-1}, {2,0}, {2,-1}}
* 输出:
* [1,-1]
思路:
典型队列问题,先进先出;使用猫和狗两个队列模拟收容所封装一个新的类型既包含动物的类型(type),又包含动物的进所时间 (time)
Tips:每次new一个动物都会调用构造函数,可在构造函数中记录进所时间,即可声明一个全局变量用作时间线
Java代码参考
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class CatDogAsylum {
static int timeline = 0;//时间线
public static void main(String[] args) {
//模拟输入样例
int[][] ope = {{1,1}, {1,-1}, {2,0}, {2,-1}};//4r2l
Queue<Animal> dogs = new LinkedList<Animal>();
Queue<Animal> cats = new LinkedList<Animal>();
ArrayList<Integer> ans = new ArrayList<Integer>();
for(int i = 0; i < ope.length; i++) {
int op = ope[i][0];//1-进;2-出
int typeNumber = ope[i][1];//0,-1猫,1狗
if(op == 1) {//进所
if(typeNumber > 0) {//+狗进所-编号
dogs.add(new Animal(typeNumber));
}else {//-猫进所
cats.add(new Animal(typeNumber));
}
}else if(op == 2) {//出所
if(typeNumber == 0) {//最先进队的出-任意动物
if((!dogs.isEmpty())&&(cats.isEmpty()
||dogs.peek().time < cats.peek().time))
ans.add(dogs.poll().type);//不是非法操作,且狗最早进所,出狗
if((!cats.isEmpty())&&(dogs.isEmpty()
||cats.peek().time < dogs.peek().time))
ans.add(cats.poll().type);//同理,猫出所
}
if(typeNumber == 1) {//收养狗
if(!dogs.isEmpty())
ans.add(dogs.poll().type);
}
if(typeNumber == -1) {//收养猫
if(!cats.isEmpty())
ans.add(cats.poll().type);
}
}
}
System.out.println(ans);
}
private static class Animal{
int type;
/**
* 动物类型编号--最后要输出的结果
*/
int time;
/**
* 动物进所时间
*/
public Animal(int type) {
super();
this.type = type;
this.time = timeline++;//每次new一个新动物时自动加时间
}
}
}
网友评论