猫狗收容所 牛客网 程序员面试金典 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:480k vector<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; 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) pop_queue(cat,ret); if(min==1) pop_queue(dog,ret); } if(item[1]==1&&!dog.empty()) pop_queue(dog,ret); if(item[1]==-1&&!cat.empty()) 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; 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; } };
转载于:https://www.cnblogs.com/vercont/p/10210312.html
