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

51 阅读 0 评论 34 点赞

我是靠谱客的博主甜美帽子，最近开发中收集的这篇文章主要介绍《程序员面试金典》猫狗收容所，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://www.nowcoder.com/practice/6235a76b1e404f748f7c820583125c50?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 here
            vector<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;
        }
};