本文共 3128 字，大约阅读时间需要 10 分钟。

问题描述

在一个动物收容所中，只收留猫和狗。收养人有两种收养方式：第一种是直接收养所有动物中最早进入收容所的；第二种是选择收养特定类型的动物（猫或狗），并收养该种动物中最早进入收容所的。操作序列由两个数组成，每个数组的第一个元素表示事件类型，第二个元素表示具体信息。

思路分析

为了按时间顺序处理事件并记录收养顺序，我们需要使用两种数据结构来分别存储猫和狗，并且记录它们的进入时间。使用队列数据结构可以高效地处理先进先出的操作。每当处理事件时，根据事件类型决定下一步操作：

为了记录动物进入的时间，可以在每个动物对象中设置一个时间属性，并在创建对象时记录当前的时间。

具体代码

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}, {2, 0}, {2, -1},
            {2, 0}
        };
        System.out.println(catAndDogAsylum(data));
    }
    private static ArrayList
   
     catAndDogAsylum(int[][] data) {
        Queue
    
      cats = new LinkedList<>();
        Queue
     
       dogs = new LinkedList<>();
        ArrayList
      
        res = new ArrayList<>();
        for (int[] opVal : data) {
            int opCode = opVal[0];
            int value = opVal[1];
            if (opCode == 1) {
                if (value > 0) {
                    Animal dog = new Animal(value);
                    dogs.add(dog);
                } else 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()) {
                        Animal dogPeek = dogs.peek();
                        Animal catPeek = cats.peek();
                        if (dogPeek.time > catPeek.time) {
                            res.add(catPeek.typeNumber);
                            cats.poll();
                        } else {
                            res.add(dogPeek.typeNumber);
                            dogs.poll();
                        }
                    }
                }
            } else {
                break;
            }
        }
        return res;
    }
}
      
     
    
   

结果解释

通过上述代码，我们可以处理给定的操作序列，返回符合收养规则的动物编号序列。代码中使用了两种队列分别存储猫和狗，并且每个动物对象记录了进入收容所的时间。根据事件类型和具体值，正确地从队列中取出动物，形成最终的收养序列。