猫狗收容所（队列）

56 阅读 0 评论 37 点赞

我是靠谱客的博主坚定冷风，最近开发中收集的这篇文章主要介绍猫狗收容所（队列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 问题描述：

有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，
第一种为直接收养所有动物中最早进入收容所的，
第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。

给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。
若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；
若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式(最早进入收容所的猫/狗)，
若为1，则指定收养狗，若为-1则指定收养猫。
请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

测试样例：

[[1,1],[1,-1],[2,0],[2,-1]]

返回：[1,-1]

2. 思路分析：① 从题目中我们可以知道需要按照时间顺序求解出收养动物编号的序列，而且控制台输入的情况不同，对应的收养情况也会不同，其实这里蕴含着某种数据结构的特点，为“先进先出”，先进来的动物是最早可能被收养的，所以我们可以使用队列这种数据结构来存储其中的数据

② 我们可以使用两个队列，一个是猫的队列，一个是狗的队列这样可以方便我们入队和出队，当操作序列的第一个元素为1的时候我们就入队，根据操作序列的第二个元素我们可以知道入的是猫队还是狗队

当操作序列的第一个元素为2的时候我们需要出队，根据操作序列的第二个元素假如元素为1而且狗队里面的元素不为空的话我们就从狗队里面出一个元素，元素为-1而且猫队里面的元素不为空的话我们就从猫队里面出一个元素

元素为0的时候这个时候就要比较猫的队首元素和狗的队首元素入收容所的时间，怎么样知道这个时间呢？我们知道进入队列肯定时间有先有后那么我们可以在入队的时候就记录这个时间，等到查看队首元素的时候我们就知道这个时间了然后进行比较就可以了

③ 我们可以在一开始创建队列的时候就可以把队列里面的数据类型设置为一个对象，利用对象可以封装对应的属性的特点，往对象中增加时间这个属性这样我们就可以在一创建这个对象的时候就把入队的时间进行记录下来，这里可以使用设置一个全局变量来进行时间的记录，然后再创建对象的时候这个全局变量的值加一然后赋值给这个对象中的时间属性，注意这里的类是私有的内部类，而且必须声明成static

private static class Animal{
	private int typeNumber;
	private int time;
	public Animal(int typeNumber) {
		super();
		this.typeNumber = typeNumber;
		this.time = timeCur++;
	}
	@Override
	public String toString() {
		return "Animal [typeNumber=" + typeNumber + ", time=" + time + "]";
	}	
}

这样我们就在查看两个队列的队首元素的时候就知道入队的时间先后顺序了

凡是涉及到要封装属性的都可以使用私有的内部类来进行记录和处理，接下里就是根据题目的要求进行简单的逻辑判断入队，出队即可，比较时间的先后顺序即可

3. 具体的代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main{
	private static int timeCur = 1;
	private static class Animal{
		private int typeNumber;
		private int time;
		public Animal(int typeNumber) {
			super();
			this.typeNumber = typeNumber;
			this.time = timeCur++;
		}
		@Override
		public String toString() {
			return "Animal [typeNumber=" + typeNumber + ", time=" + time + "]";
		}	
	}
	
	public static void main(String[] args) {
		 int[][] data = {{1, 1}, {1, -1}, {1, 0}, {1, 1}, {1, -5}, {2, 0}, {2, -1}, {2, 0}};
		 System.out.println(catAndDogAsyLum(data));
	}
	
	private static ArrayList<Integer> catAndDogAsyLum(int opValue[][]){
		Queue<Animal> cats = new LinkedList<Animal>();
		Queue<Animal> dogs = new LinkedList<Animal>();
		ArrayList<Integer> res = new ArrayList<Integer>();
		for(int opVal[] : opValue){
			int opCode = opVal[0];
			int value = opVal[1];
			if(opCode == 1){
				if(value > 0){
					Animal dog = new Animal(value);
					dogs.add(dog);
				}
				if(value < 0){
					Animal cat = new Animal(value);
					cats.add(cat);
				}
			}else if(opCode == 2){
				if(!dogs.isEmpty() && value == 1){
					res.add(dogs.poll().typeNumber);
				}
				if(!cats.isEmpty() && value == -1){
					res.add(cats.poll().typeNumber);
				}
				if(value == 0){
					if(dogs.isEmpty() &&  !cats.isEmpty()){
						res.add(cats.poll().typeNumber);
					}
					else if(!dogs.isEmpty() && cats.isEmpty()){
						res.add(dogs.poll().typeNumber);
					}else if(!dogs.isEmpty() && !cats.isEmpty()){
						int type = dogs.peek().time >  cats.peek().time ? cats.poll().typeNumber: dogs.poll().typeNumber;
						res.add(type);
					}
				}
			}else{
				break;
			}
		}
		return res;
	}
}