文档章节

猫狗收容所

e
 eversliver
发布于 2016/08/12 11:24
字数 671
阅读 13
收藏 0
  • 有家动物收容所只收留猫和狗,但有特殊的收养规则,收养人有两种收养方式,第一种为直接收养所有动物中最早进入收容所的,第二种为选择收养的动物类型(猫或狗),并收养该种动物中最早进入收容所的。 给定一个操作序列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
        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;
    }
};

吐槽一下,题干太长了

© 著作权归作者所有

共有 人打赏支持
e
粉丝 0
博文 57
码字总数 10582
作品 0
成都
动物收容所,先进先出

有家动物收容所只收容狗与猫,且严格遵守“先进先出”原则。在收养该收容所的动物时,收养人只能收养进入收容所时间最长的动物,或者,挑选猫或狗中收养时间最长的。 请创建适合这个系统的数...

一贱书生
2016/11/17
25
0
java 接口(interface)的意义

接口的作用对于很多新手来说很不容易理解,我给大家举个例子。 接口只是一个规范,所以里面的方法都是空的。 假如我开了一个宠物粮店,声明所有宠物都可以来我这里买粮食,这就相当于一个接口...

梅超疯
2013/11/26
0
0
神奇!!!人工智能竟然是模拟人脑设计出来的

神奇!!!人工智能竟然是模拟人脑设计出来的 人工智能的实现主要依靠于两个方面。第一个方面是数学建模,也就是软件跟算法,这需要很高深的一个数学跟神经学的原理。第二个是大数据的喂养。...

朱有鹏老师
01/17
0
0
使用CUBE和ROLLUP对数据进行汇总

  想要找一个既快捷又有效的方法来对您存储在数据库里的数据进行汇总分析吗?SQL语言中的ROLLUP和CUBE命令提供了一个非常有用的工具,可以让您快速深入地获取数据的各种内在性质。ROLLUP和C...

Adairs
2016/03/10
2
0
迁移学习基础知识 源域 多任务学习 目标域

迁移学习 简单的将就是举一反三,是将已经学习到的知识迁移到另一种未知的知识的学习,即从源域迁移到目标域。 小故事 从前有一个商人,在帝都以卖猫的玩偶为生,他叫CNN,很厉害,是一个分辨...

superyr_210
01/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
今天
2
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
今天
3
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
15
0
GRASP设计模式

此文参考了这篇博客,建议读者阅读原文。 面向对象(Object-Oriented,OO)是当下软件开发的主流方法。在OO分析与设计中,我们首先从问题领域中抽象出领域模型,在领域模型中以适当的粒度归纳...

克虏伯
昨天
1
0
Coding and Paper Letter(四十)

资源整理。 1 Coding: 1.Tomislav Hengl撰写的非官方作者指南:Michael Gould•Wouter Gerritsma。 UnofficialGuide4Authors 2.R语言包rwrfhydro,社区贡献的工具箱,用于管理,分析和可视化...

胖胖雕
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部