《程序员面试金典》猫狗收容所

题目链接：?rp=1&ru=/ta/cracking-the-coding-interview&qru=/ta/cracking-the-coding-interview/question-ranking

题目描述有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，整数代表狗，负数代表猫；若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式，若为1，则指定收养狗，若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作，，即没有可以符合领养要求的动物，则将这次领养操作忽略。测试样例：[[1,1],[1,-1],[2,0],[2,-1]]返回：[1,-1]思路我们使用两个队列来完成所有的操作，对于第一种操作，我们只需要返回队列中第一个元素即可对于第二个操作，我们就将所有不符合要求的数据存入辅助队列中，一直找到第一个满足条件的元素，那么就删除，然后再将辅助队列所有元素又归还原队列

class CatDogAsylum{public:vector<int> asylum(vector<vector<int> > ope){// write code herevector<int> ans;int len = ope.size();if(len==0)return ans;queue<int> Q1;queue<int> Q2;for(int i = 0; i<len; i++){if(ope[i][0]==1){Q1.push(ope[i][1]);}else{if(ope[i][1]==0){if(!Q1.empty()){ans.push_back(Q1.front());Q1.pop();}}else{while(!Q1.empty()){if(ope[i][1]<0 && Q1.front()<0){ans.push_back(Q1.front());Q1.pop();break;}else if(ope[i][1]>0 && Q1.front()>0){ans.push_back(Q1.front());Q1.pop();break;}else{Q2.push(Q1.front());Q1.pop();}}while(!Q1.empty()){Q2.push(Q1.front());Q1.pop();}while(!Q2.empty()){Q1.push(Q2.front());Q2.pop();}}}}return ans;}};

每一件事与每一个美丽景色，都有可能成为一生中的难忘。

相关文章：

你感兴趣的文章：

标签云：