猫狗收容所 牛客网 程序员面试金典 C++

猫狗收容所 牛客网 程序员面试金典 C++

猫狗收容所 牛客网 程序员面试金典 C++

• 题目描述

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

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

• 测试样例：

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

• 返回：[1,-1]

C++

class CatDogAsylum {
public://run:4ms memeory:480kvector<int> asylum(vector<vector<int> > ope) {queue<int> cat;queue<int> dog;vector<int> ret;int index=0;for(int i = 0; i < ope.size(); i++){vector<int> item = ope[i];if(item[0] == 1)if(item[1] >= 0) push_queue(dog,item[1],index++);else push_queue(cat,item[1],index++);if(item[0] == 2){if(item[1] == 0){int min=0;pty() && !pty()) min=1;if(!pty() && pty()) min=-1;if(!pty() && !pty()) min=dog.front() > cat.front() ? -1:1;if(min==-1) pop_queue(cat,ret);if(min==1) pop_queue(dog,ret);      }if(item[1]==1&&!pty()) pop_queue(dog,ret);if(item[1]==-1&&!pty()) pop_queue(cat,ret);}}return ret;}void push_queue(queue<int> &q, int value,int index){q.push(index);q.push(value);}void pop_queue(queue<int> &q,vector<int> &ret){q.pop();ret.push_back(q.front());q.pop();}vector<int> asylum2(vector<vector<int> > ope) {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;pty()&&!pty()) min=1;if(!pty()&&pty()) min=-1;if(!pty()&&!pty()) 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&&!pty()){dog.pop();vec.push_back(dog.front());dog.pop();}if(ope[i][1]==-1&&!pty()){cat.pop();vec.push_back(cat.front());cat.pop();}}}}return vec;}
};