首页 > 试题广场 > 猫狗收容所
[编程题]猫狗收容所
  • 热度指数:16707 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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

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

测试样例:
[[1,1],[1,-1],[2,0],[2,-1]]
返回:[1,-1]
推荐
思路:定义两个vector<int>对象A和B,分别用于存放收容所里的动物和被收养的动物
操作如下:
对ope数组从按行从i = 0 ~ ope.size() -1遍历
1、指令为1(ope[i][0] = 1)时,即有动物进来,则将动物序号压入A--执行A.push_back(ope[i][1]);
2、指令为2(ope[i][0] = 2)时,即有动物被收养,此时首先判断A是否为空,即是否有动物
    1)如果A为空,则continue
    2)如果A不为空
        1.如果操作为ope[i][1] = 0,即收养最先进来的动物,则将A[0]压入B,执行B.push_back(A[0]),然后在A中删除对应元素,即执行A.erase(A.begin());
        2.如果操作为ope[i][1] = 1,即收养最先进来的狗,此时遍历A找到第一个狗,然后将找到的元素压入B,再在A中删除对应元素;
        3.如果操作为ope[i][1] = -1,即收养最先进来的猫,此时遍历A找到第一个猫,然后将找到的元素压入B,再在A中删除对应的元素。
遍历完成之后,返回B。
代码如下所示:
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        vector<int> A;   //定义动物序列
        vector<int> B;   //定义收养序列
        int i;     //定义循环变量
        int len = ope.size();
        for(i = 0; i < len; i ++)
            {
            if(ope[i][0] == 1) //有动物进来
                A.push_back(ope[i][1]);  //放入动物序列
            else
                if(A.empty())
                 continue;
                else
                 if(ope[i][1] == 0)  //第一种收养方式
                  {
                     B.push_back(A[0]);
                     A.erase(A.begin()); //从A中删除对应元素
                 }
              else
                     if(ope[i][1] == 1)  //收养狗
                     {
                         for(int j = 0; j < A.size(); j ++)
                       if(A[j] > 0)
                       {
                        B.push_back(A[j]);
                        A.erase(A.begin() + j); //从A中删除对应元素
                        break;
                    }
                     }
               else
                            for(int j = 0; j < A.size(); j ++)
                       if(A[j] < 0)
                       {
                        B.push_back(A[j]);
                        A.erase(A.begin() + j); //从A中删除对应元素
                        break;
                    }
        }
        return B;
    }
};
          
编辑于 2015-08-18 20:08:14 回复(4)
import java.util.*;

public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
       ArrayList<Integer> input = new ArrayList<Integer>();
        ArrayList<Integer> output = new ArrayList<Integer>();
        int rows = ope.length;
        for(int i = 0;i<rows;i++){
        	switch(ope[i][0]){
        	//有动物进入
        	case 1:
        		input.add(ope[i][1]);
        		break;
        	//有人领养
        	case 2:
        		//第一种领养方式
        		if(ope[i][1] == 0){
        			for(int j = 0; j<input.size();j++){
        				if(input.get(j) != 0){
        					output.add(input.get(j));
        					input.set(j, 0);
        					break;
        				}
        			}
        		}
        		//指定收养狗
        		else if(ope[i][1]==1){
        			for(int j = 0; j<input.size();j++){
        				if(input.get(j) > 0){
        					output.add(input.get(j));
        					input.set(j, 0);
        					break;
        				}
        			}
        		}
        		//指定收养猫
        		else if(ope[i][1]== -1){
        			for(int j = 0; j<input.size();j++){
        				if(input.get(j) < 0){
        					output.add(input.get(j));
        					input.set(j, 0);
        					break;
        				}
        			}
        		}
        		break;
        	}
        }
        return output;
    }
}

发表于 2016-06-23 23:47:52 回复(3)

题目分析:

  根据先进先出的原则,自然想到了用队列实现,如果只维护一个队列,那么第一种方法实现起来比较简单,只需要取出队头的动物则可以,但是第二种方法就比较复杂,需要访问整个队列来找出第一个被访问的猫或者狗。

  因此我们可以选择维护两个队列来实现,一个队列存放放入的狗,一个队列存放放入的猫,对于第二种方法实现起来相当容易,我们只需要根据要选择的猫或者狗从相应的队列中取出便可以,但是第一种方法需要判断那个两个队列头部的是猫先进入收容所,还是狗先进入,这个时候需要一个标志,所以我们每次把动物放入队列的时候,同时将一个递增的序号放入队列,这个序号就是一个时间序列,根据这个序号便可以轻松实现第一种方法。
《程序员面试金典》--题目详解:
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
		queue<int> cat;
		queue<int> dog;
		vector<int> vec;
		int index=0;
		int size1=ope.size();
		for(int i=0;i<size1;i++)
		{
			int kind=ope[i][0];
			if(kind==1)
			{
				if(ope[i][1]>=0)
				{
					dog.push(index++);
					dog.push(ope[i][1]);
				}
				else
				{
					cat.push(index++);
					cat.push(ope[i][1]);
				}
			}
			else
			{
				if(ope[i][1]==0)
				{
					int min=0;
					if(cat.empty()&&!dog.empty())
						min=1;
					if(!cat.empty()&&dog.empty())
						min=-1;
					if(!cat.empty()&&!dog.empty())
						min=dog.front()>cat.front()?-1:1;
					if(min==-1)
					{
						cat.pop();
						vec.push_back(cat.front());
						cat.pop();
					}
					if(min==1)
					{
						dog.pop();
						vec.push_back(dog.front());
						dog.pop();
					}
				}
				else
				{
					if(ope[i][1]==1&&!dog.empty())
					{
						dog.pop();
						vec.push_back(dog.front());
						dog.pop();
					}
					if(ope[i][1]==-1&&!cat.empty())
					{
						cat.pop();
						vec.push_back(cat.front());
						cat.pop();
					}
				}

			}
		}
		return vec;
    }
};

发表于 2015-10-05 16:58:10 回复(2)
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;
	}

发表于 2016-04-05 16:10:43 回复(1)
public ArrayList<Integer> asylum(int[][] ope) {
         // write code here
         ArrayList<Integer> r = new ArrayList<Integer>();// 存放最终收养序列
         ArrayList<Integer> animal = new ArrayList<Integer>();// 存放进入收容所的动物
         int temp=0;
         for (int i = 0; i < ope.length; i++) {
             switch (ope[i][0]) {
             // 有动物进入收容所
             case 1:
                 animal.add(ope[i][1]);
                 break;
             // 有人收养动物
             case 2:
                 // 第一种收养方式
                 if (!animal.isEmpty()&&ope[i][1] == 0) {
                     r.add(animal.get(0));
                     animal.remove(0);
                 } 
                 // 收养狗
                 else if (ope[i][1] == 1) {
                     for(temp=0;temp<animal.size();temp++){
                         if(animal.get(temp)>0){
                             r.add(animal.get(temp));
                             animal.remove(temp);
                             break;
                         }
                     }
                 }
                 // 收养猫
                 else if(ope[i][1] == -1){
                     for(temp=0;temp<animal.size();temp++){
                         if(animal.get(temp)<0){
                             r.add(animal.get(temp));
                             animal.remove(temp);
                             break;
                         }
                     }
                 }
                 break;
             }
         }
         return r;
     }

编辑于 2017-02-25 10:35:37 回复(2)
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        queue<int> dog, cat;//狗和猫各一个队列
        vector<int> res;
        queue<int> dogOrder, catOrder;//狗和猫顺序各一个队列
        for(unsigned int i = 0; i < ope.size(); ++i){
            if(ope[i][0] == 1){//有新动物进来
                if(ope[i][1] > 0){//狗
                    dog.push(ope[i][1]);//狗的编号
                	dogOrder.push(i);//记录狗是第几个进来的
                }
                else if(ope[i][1] < 0){//猫的情况类似
                    cat.push(ope[i][1]);
                    catOrder.push(i);
                }
            }
            else if(ope[i][0] == 2){ //有人收养动物
                int num = 0;//记录收养动物的编号
                if( ope[i][1] == 0 && (dog.size() || cat.size())){//可以收养
                	if(dog.size() > 0 && cat.size() == 0){
                        num = dog.front();//猫没了
                        dog.pop();
                    }
                	else if(dog.size() == 0 && cat.size() > 0){
                    	num = cat.front();//狗没了
                        cat.pop();
                    }
                	else if(dogOrder.front() < catOrder.front()){
                        num = dog.front();//狗进来得早
                        dog.pop();
                    }
                	else if(dogOrder.front() > catOrder.front()){
                        num = cat.front();//猫进来得早
                        cat.pop();
                    }  
            	}
                else if(ope[i][1] == 1 && dog.size()){
                    num = dog.front();//指定收养狗
                    dog.pop();
                }
                else if(ope[i][1] == -1 && cat.size()){
                    num = cat.front();//指定收养猫
                    cat.pop();
                }
                
                if(dog.size() != dogOrder.size())//检查长度
                    dogOrder.pop();
                if(cat.size() != catOrder.size())
                    catOrder.pop();
                if(num) res.push_back(num);//num不为0说明收养成立
            }
        }
        return res;
    }
};

发表于 2015-10-01 00:42:02 回复(0)
import java.util.*;

public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        if (ope == null || ope.length == 0 || ope[0] == null || ope[0].length == 0) {
            return res;
        }
        Queue<Integer> dog = new LinkedList<>();
        Queue<Integer> cat = new LinkedList<>();
        Queue<Integer> all = new LinkedList<>();
        for (int i = 0; i < ope.length; i++) {
            if (ope[i][0] == 1) { //有动物进收容所
                if (ope[i][1] > 0) { //狗
                    dog.add(ope[i][1]);
                    all.add(ope[i][1]);
                } else if (ope[i][1] < 0) { //猫
                    cat.add(ope[i][1]);
                    all.add(ope[i][1]);
                }
            } else if (ope[i][0] == 2) { //有人收养宠物
                if (ope[i][1] == 0) { //第1种方式
                    if (!all.isEmpty()) {
                        int temp = all.poll();
                        res.add(temp);
                        if (temp > 0) {
                            dog.poll();
                        } else {
                            cat.poll();
                        }
                    }
                } else if (ope[i][1] == 1) { //狗
                    if (!dog.isEmpty()) {
                        int temp = dog.poll();
                        res.add(temp);
                        all.remove(temp);
                    }
                } else if (ope[i][1] == -1) { //猫
                    if (!cat.isEmpty()) {
                        int temp = cat.poll();
                        res.add(temp);
                        all.remove(temp);
                    }
                }
            }
        }
        return res;
    }
}

发表于 2019-11-28 02:21:29 回复(0)
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为10.00%
用例:
[[1,-7],[1,-4],[1,1],[1,1],[2,0],[1,75],[2,1],[2,-1],[1,21],[1,-83],[2,0],[2,-1],[1,7],[1,-64],[1,73],[2,-1],[1,1],[2,1],[1,58],[1,34],[1,-13],[1,-78],[1,21],[1,50],[2,0],[1,-23],[1,76],[1,89],[2,-1],[1,5],[1,18],[1,-45],[2,1],[1,-15],[2,-1],[2,-1],[2,0]]

测试数据里面的编号居然有重复的,这也是有效的case???
发表于 2019-07-20 12:33:49 回复(0)
struct Animal {
    int animal;
    int valid;
    Animal(int x) : animal(x), valid(true) {}
};
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        queue<Animal *> cat, dog, animal;
        vector<int > res;
        for (int i = 0; i < ope.size(); ++i) {
            switch (ope[i][0]){
                case 1: {
                    auto *a = new Animal(ope[i][1]);
                    animal.push(a);
                    if (ope[i][1] > 0) {
                        dog.push(a);
                    } else {
                        cat.push(a);
                    }
                    break;
                }
                case 2: {
                    if (ope[i][1] == 0) {
                        while (!animal.empty()){
                            auto a = animal.front(); animal.pop();
                            if(a ->valid){
                                res.push_back(a -> animal);
                                a -> valid = false;
                                break;
                            }
                        }
                    }
                    else if(ope[i][1] == 1) {
                        while (!dog.empty()){
                            auto a = dog.front(); dog.pop();
                            if(a ->valid){
                                res.push_back(a -> animal);
                                a -> valid = false;
                                break;
                            }
                        }
                    } else{
                        while (!cat.empty()){
                            auto a = cat.front(); cat.pop();
                            if(a ->valid){
                                res.push_back(a -> animal);
                                a -> valid = false;
                                break;
                            }
                        }

                    }
                    break;
                }
            }
        }
        return res;
    }
};

//懒人模拟大法~

发表于 2019-06-10 15:07:55 回复(0)

本来用了三个队列,猫/狗/所有, 第一类领养时,维护所有队列清除已经被领养的.但是谁曾想编号不是唯一的,换用时间戳了,缺乏美感.

class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        queue<pair<int,int>> cat;
        queue<pair<int,int>> dog;
        vector<int> res;
        int uuid = 0;
        for (auto op : ope) {
            switch (op[0]) {
                case 1:
                    if(op[1] > 0) dog.push(make_pair(op[1],uuid++));
                    else cat.push(make_pair(op[1],uuid++));
                    break;
                case 2:
                    int tp = op[1];
                    if(tp == 0) {
                        int d = dog.empty() ? INT_MAX : dog.front().second;
                        int c = cat.empty() ? INT_MAX : cat.front().second;
                        if (d < c) {
                            res.push_back(dog.front().first);
                            dog.pop();
                        } else if (d > c) {
                            res.push_back(cat.front().first);
                            cat.pop();
                        }
                    }
                    if(tp == 1) {
                        if(!dog.empty()){
                            res.push_back(dog.front().first);
                            dog.pop();
                        }
                    }
                    if(tp == -1){
                        if (!cat.empty()){
                            res.push_back(cat.front().first);
                            cat.pop();
                        }
                    }
                    break;
            }
        }
        return res;
    }
};
编辑于 2019-02-27 23:15:03 回复(0)

# -*- coding:utf-8 -*-
class CatDogAsylum:
    def asylum(self, ope):
        s = []
        res = []
        for v in ope:
            if v[0] == 1:
                s.append(v[1])
            else:
                if v[1] == 0 and s:
                    res.append(s.pop(0))
                else:
                    for i, si in enumerate(s):
                        if v[1] * si > 0:
                            res.append(s.pop(i))
                            break
        return res

运行时间:59ms

占用内存:5732k

发表于 2018-12-24 17:49:06 回复(1)
思路:

定义两个vector<int> animal , result; 分别用于存放收容所的动物和 被收养的动物。
遍历 ope:
如果第一个元素为 1:表示有新的动物要来,将动物的编号直接加入animal中。
如果第一个元素为 2:表示有人收养动物,
        如果第二个元素为0:  
            animal 非空:弹出第一个元素并将其加入result 中,删除对 应元素;
            animal 为空:滤过。
        如果第二个元素为1 或 -1: 
            遍历 animal ,当遇到第一个 ope[i][1] * animal[index] > 0 的元素的时候,
            将animal[index] 加入 result中,并删除animal 中对应的元素。


#include <iostream>
#include <vector>

using namespace std;

class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        vector<int> animal;
        vector<int> result;
        for(int i = 0; i < ope.size(); ++i)
        {
            // 有动物进来
            if(ope[i][0] == 1)
            {
                animal.push_back(ope[i][1]);
            }
            // 有动物出去
            else if(ope[i][0] == 2)
            {
                // 最早来的动物出去
                if(ope[i][1] == 0)
                {
                    if(animal.size() > 0)
                    {
                        result.push_back(animal[0]);
                        animal.erase(animal.begin());
                    }
                }
                // 指定某种动物,最早来的此种动物出去
                else 
                {
                    int index = -1;
                    for(int j = 0; j < animal.size(); ++j)
                    {
                        if(animal[j] * ope[i][1] > 0)
                        {
                            index = j;
                            result.push_back(animal[index]);
                            animal.erase(animal.begin() + index);
                            break;
                        }
                    }
                    
                }
            }
            else
            {
                continue;
            }
        }
        
        return result;
    }
};

编辑于 2018-07-24 17:11:34 回复(0)
import java.util.*;

public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        // write code here
        //定义LinkedList 用来保存猫狗,相当于收容所,ArrayList 用来保存领养的猫狗。
        LinkedList<Integer> ll = new LinkedList<Integer>();
        ArrayList<Integer> al = new ArrayList<Integer>();
        if(ope==null||ope.length==0||ope[0].length==0){
            return al;
        }
        //如果ope[i][0]==1,进入收养所
        for(int i=0 ; i<ope.length;i++){
            if(ope[i][0]==1){
                ll.add(ope[i][1]);
            }
            if(ope[i][0]==2){  //需要出所
                if(ope[i][1]==0){ //方式1
                    al.add(ll.remove(0));
                }else if(ope[i][1]==1){//收养狗
                    for(int j=0;j<ll.size();j++){
                        if(ll.get(j)>0){
                            al.add(ll.remove(j));
                            break;
                        }
                    }
                }else{  //收养猫
                    for(int j=0;j<ll.size();j++){
                        if(ll.get(j)<0){
                            al.add(ll.remove(j));
                            break;
                        }
                    }
                }
            }
        }
        return al;
         
    }
}

发表于 2017-12-22 10:45:51 回复(0)
import java.util.ArrayList;
import java.util.LinkedList;

public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        LinkedList<int[]> list = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<>();
        for (int[] items : ope) {

            if (items[0] == 1) {
                // 如果遇到宠物就加入列表中(收容所)
                list.add(items);
            } else if (items[0] == 2) {
                // 如果遇到收养人
                // 采取第一种收养方式
                if (items[1] == 0) {
                    if (!list.isEmpty()) {
                        int[] animal = list.remove(0);
                        res.add(animal[1]);
                    }
                } else {
                    // 收取猫或狗(若为1,则指定收养狗,若为-1则指定收养猫)
                    for (int i = 0; i < list.size(); i++) {
                        // 收容所有合适宠物则弹出
                        if ((items[1] == 1 && list.get(i)[1] > 0) || (items[1] == -1 && list.get(i)[1] < 0)) {
                            // 移除宠物
                            int[] animal = list.remove(i);
                            res.add(animal[1]);
                            // 结束本层循环
                            break;
                        }
                    }
                }
            }
        }
        return res;
    }
}
发表于 2017-10-01 00:56:07 回复(0)
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class Animal{
	int order;
	int name;
public:
	Animal(int n) :name(n){}

	void setOrder(int n){
		order = n;
	}
	int getName(){
		return name;
	}
	int getOrder(){
		return order;
	}
};

class CatDogAsylum {
public:
	vector<int> asylum(vector<vector<int> > ope) {
		if (ope.size() == 0)
			return vector<int>();

		vector<int> res;

		for (unsigned int i = 0; i < ope.size(); ++i){
			if (ope[i][0] == 1){
				if (ope[i][1] > 0){
					Animal dog(ope[i][1]);
					dog.setOrder(order++);
					dogs.push(dog);
				}
				else if (ope[i][1] < 0){
					Animal cat(ope[i][1]);
					cat.setOrder(order++);
					cats.push(cat);
				}
			}
			else if (ope[i][0] == 2){
				if (ope[i][1] == 0){
					if (dogs.front().getOrder()<cats.front().getOrder()){
						res.push_back(dogs.front().getName());
						dogs.pop();
					}
					else{
						res.push_back(cats.front().getName());
						cats.pop();
					}
				}
				else if (ope[i][1] == 1 && !dogs.empty()){
					res.push_back(dogs.front().getName());
					dogs.pop();
				}
				else if (ope[i][1] == -1&&!cats.empty()){
					res.push_back(cats.front().getName());
					cats.pop();
				}
			}
		}
		return res;
	}

private:
	queue<Animal> dogs;
	queue<Animal> cats;
	int order = 0;

};

发表于 2017-08-08 16:23:17 回复(0)
知识点也提到有栈和队列
                        ArrayList<Integer> list = new ArrayList<Integer>();
			LinkedList<Integer> animal = new LinkedList<Integer>();
			Stack<Integer> st = new Stack<Integer>();
			for (int i=0; i<ope.length; i++){
				if (ope[i][0] == 1){
					if (ope[i][1] != 0){
						animal.addLast(ope[i][1]);					
					}				
				}else if(ope[i][0] == 2){
					if (ope[i][1] == 0){
						if (!animal.isEmpty())
							list.add(animal.removeFirst());
						continue;
					}
					if (ope[i][1] == 1){
						while (!animal.isEmpty()) {
							if (animal.getFirst()>0){
								list.add(animal.removeFirst());
								break;
							}else {
								st.push(animal.removeFirst());
							}					
						}
					}else if(ope[i][1] == -1){
						while (!animal.isEmpty()) {
							if (animal.getFirst()<0){
								list.add(animal.removeFirst());
								break;
							}else {
								st.push(animal.removeFirst());
							}					
						}
					}
					while (!st.isEmpty()){
						animal.addFirst(st.pop());
					}
				}
			}
			return list;

发表于 2017-07-29 23:27:30 回复(0)
//收养序列啊
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        vector<int> ans, fin;
        for(int i = 0; i < ope.size(); i++){
            if(ope[i][0] == 1){
                ans.push_back(ope[i][1]);
            }	
            if(ope[i][0] == 2 && !ans.empty()){
                if(ope[i][1] == 0 ){                   
                    fin.push_back(ans[0]);
                    ans.erase(ans.begin());
                }	
                else if(ope[i][1] > 0){
                    for(int j = 0; j < ans.size(); j++)
                        if(ans[j] > 0){
                            fin.push_back(ans[j]);
                            ans.erase(ans.begin() + j);
                            break;
                        }
                }else{
                    for(int j = 0; j < ans.size(); j++) 
                        if(ans[j] < 0){
                            fin.push_back(ans[j]);
							ans.erase(ans.begin() + j);   
                            break;
                        }	
                }
            }
        }
        return fin;
    }
};

发表于 2017-06-07 21:24:38 回复(0)
思路:采用双端队列来存储猫狗的收容所,用向量存储需要返回的收养序列
vector<int> asylum(vector<vector<int> > ope) {
	// write code here
	vector<int> ret;//领养顺序
	deque<int> myqueue;//猫狗收养所
	stack<int> temp;//用作对第二种收养方法的临时空间
	for (auto vv_elem : ope){
		if (vv_elem[0] == 1)//收养方法1
			myqueue.push_back(vv_elem[1]);
		else if (vv_elem[1] == 0 && !myqueue.empty()){//收养方法2中的0
			ret.push_back(myqueue.front());
			myqueue.pop_front();
		}
		else{
                        //当收养所与领养方法2不同号,则出队并保存到临时收养所 temp
			while (!myqueue.empty() && myqueue.front()*vv_elem[1] < 0){

				temp.push(myqueue.front());
				myqueue.pop_front();
			}
                        //找到需要被领养的动物,存入收养顺序 ret
			if (!myqueue.empty()){
				ret.push_back(myqueue.front());
				myqueue.pop_front();
			}
                        //将临时收养所 temp 放回收养所的队头front
			while (!temp.empty()){
				myqueue.push_front(temp.top());
				temp.pop();
			}
		}
	}
	return ret;
}
是不是很简洁!

发表于 2017-05-19 20:55:44 回复(1)
import java.util.*;
//表示虽然思路是有的,但是都不知道自己是怎么完成的,删删改改了老半天
//利用了一个list,如果是获得猫狗就存进来,如果是失去猫狗就分情况讨论
//按照要求顺序取出猫狗即可
//主要点就是失去猫狗的位置不能用remove方法删去,需要置0,保证list.size的不变
public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        for(int i=0;i<ope.length;i++){
            switch(ope[i][0]){
                case 1: list.add(ope[i][1]);break;	  	   
                case 2:	if(ope[i][1] ==0){
                    		int j=0;
                    		while(j<list.size()&&list.get(j)==0){
                                j++;                                
                            }
                            if(j<list.size()){ 
                                result.add(list.get(j));
                    			list.set(j,0);
                            }             			
                		}else if(ope[i][1]== -1){//取出第一只放进去的猫,猫是负数
                    		int j =0;
                    		while(j<list.size()&&list.get(j) >=0){
                                 j++;
                            }
                            if(j<list.size()){
                                result.add(list.get(j));
                                list.set(j,0);
                            }       
                		}else if(ope[i][1]== 1){//取出第一只放进去的狗,狗是正数
                    		int j =0;
                            while(j<list.size()&&list.get(j)<=0){
                                j++;
                            }
                                if(j<list.size()){
                                   result.add(list.get(j));
                                   list.set(j,0);
                                }
                		}else{
                    		continue;
                		}
                break;
            }
        }
        return result;
    }	
}
运行时间:85ms
占用内存:1232k

编辑于 2017-05-17 19:07:59 回复(0)
思路:使用双端队列,和一个辅助栈实现



classCatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
         
        deque<int> animals;
        vector<int> result;
        for(inti=0;i<ope.size();i++)
            {
             intnode=function(animals,ope[i]);
            if(node!=0)
                {
                result.push_back(node);
            }
        }
        returnresult;
    }
     
    intfunction(deque<int> & animals,vector<int> ope)
        {
         stack<int> help;
        if(ope[0]==1)
            {
            if(ope[1]!=0)
                animals.push_back(ope[1]);
            return0;
        }
        elseif(ope[0]==2&& ope[1]== 0)
            {
            if(!animals.empty())
                {
                intnode=animals.front();
                animals.pop_front();
                returnnode;
            }
            
        }
        elseif(ope[0]==2&& ope[1]== 1)
            {
 
          
            intnode=0;
            while((!animals.empty())&& animals.front()<0)
                {
                    help.push(animals.front());
                    animals.pop_front();
                }
                if(!animals.empty())
                    {
                    node=animals.front();
                    animals.pop_front();
                }
                while(!help.empty())
                    {
                        animals.push_front(help.top());
                        help.pop();
                    }
                returnnode;
                 
            }
        elseif(ope[0]==2&& ope[1]== -1)
            {
 
            intnode=0;
            while((!animals.empty())&& animals.front()>0)
                {
                    help.push(animals.front());
                    animals.pop_front();
                }
                if(!animals.empty())
                    {
                    node=animals.front();
                    animals.pop_front();
                }
                while(!help.empty())
                    {
                        animals.push_front(help.top());
                        help.pop();
                }
                returnnode;
                 
            }
        else
            {
            return0;
        }
         
        return0;
         
    }
};
发表于 2017-05-02 22:59:11 回复(0)
vector<int> asylum(vector<vector<int> > ope) 
{
	deque<int> animal;
	deque<int> dogorcat;	// animal中猫狗用正负1表示的一个映射
	vector<int> ret;
	if (ope.size() == 0)
		return ret;
	int num = ope.size();
	for (int i = 0; i < num; i++)
	{
		int fir = ope[i][0];
		int sec = ope[i][1];
		if (fir == 1)
		{
			animal.push_back(sec);
			dogorcat.push_back(sec > 0 ? 1 : -1);
		}
		else if (fir == 2)
		{
			if (animal.size() == 0)
				continue;
			if (sec == 0)
			{
				int x = animal.front();
				animal.pop_front();
				dogorcat.pop_front();
				ret.push_back(x);
			}
			else
			{
				deque<int>::iterator iter = find(dogorcat.begin(), dogorcat.end(), sec);
				if (iter == dogorcat.end())
					continue;
				int cnt = iter - dogorcat.begin();
				dogorcat.erase(iter);
				iter = animal.begin();
				iter += cnt;
				ret.push_back(*iter);
				animal.erase(iter);
			}
		}
	}
	return ret;
}

发表于 2017-04-18 20:58:03 回复(0)

问题信息

难度:
113条回答 19475浏览

热门推荐

通过挑战的用户

查看代码