首页 > 分享 > 动物收容所领养策略

动物收容所领养策略

萌宠菠菠乐园
2024-12-28 16:37

一、题目

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

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

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

[1,-1]
牛客网题目链接

二、题目分析

已知规则：[left,right]

left = 0 代表有动物进入收容所
right > 0 代表狗
right < 0 代表猫
left = 1 代表有动物被收养
right = 0 表示收养最早来到收容所的动物
right = 1表示收养最早来到收容所的狗
right = -1 表示收养最早来到收容所得猫
需要返回被收养动物列表

牛客网提示，使用到栈和队列的知识，但是我觉得用不上。这里只是有"先进先出"（先收留的动物先收养）的动作。实际上，用到队列，就得考虑用几个队列，由于先进先出，若收养的第一个动物是队首元素后面的动物，这样看，一个队列是行不通的，如果有两个队列，两个队首（猫和狗的队列）的动物，谁是第一个来到收容所的？这样显得有些麻烦，返回值是一个ArrayList(),那么我们考虑是不是能通过构造in，out两个ArrayList来实现这样一个过程。通过遍历数组，来模拟上面的操作。具体过程见代码。

三、代码

import java.util.*; public class CatDogAsylum { public ArrayList<Integer> asylum(int[][] ope) { // write code here // 第一个元素：1 进入 // 2 有人收养 // 第二个元素：正数狗 // 负数猫 // 0 策略一：选择最早的 // 1 狗、 // -1 猫 ArrayList<Integer> in = new ArrayList<>(); ArrayList<Integer> out = new ArrayList<>(); for (int i = 0; i < ope.length; i++) { if (ope[i][0] == 1){ // 1，让所有的动物进入in这个列表中 // 遍历每一行，查看其第一个元素是否为1，是1就说明，需要进入列表之中. // 将对应的动物编号添加进列表 in.add(ope[i][1]); }else if (ope[i][0] == 2){ // 2, 如果第一个元素为2 的话，需要判断删除列表中的那个动物 if (in.isEmpty()){ continue; }else if (ope[i][1] == 0){ // 按照策略一，取出第一个动物 out.add(in.get(0)); in.remove(0); }else if (ope[i][1] == 1){ // 遍历in列表，找到第一个需要被收养的狗 for (int j = 0; j < in.size(); j++) { if (in.get(j) > 0){ out.add(in.get(j)); in.remove(j); // 找到第一个需要被收养的狗，就结束当前循环 break; } } }else if (ope[i][1] == -1){ // 遍历in列表，找到第一个需要被收养的猫 for (int j = 0; j <in.size() ; j++) { if (in.get(j) < 0){ out.add(in.get(j)); in.remove(j); // 找到第一个需要被收养的猫，就接受当前循环 break; } } } } } return out; } }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455