文档章节

猫狗收养所

r
 ranjiewen
发布于 2016/11/03 23:48
字数 1252
阅读 5
收藏 0
      两种方法实现,用两个vector实现,一个为领养的动物(输出),一个为收养的动物(输入);用两个queue实现(都为输入),一个为收养的猫,一个收养的狗,vetor(输出)。

/*****************************************************
* \file CatDogAsylum.cpp
* \date 2016/05/09 15:19

* \问题描述:
题目描述

有家动物收容所只收留猫和狗,但有特殊的收养规则,收养人有两种收养方式,第一种为直接收养所有动物中最早进入收容所的,
第二种为选择收养的动物类型(猫或狗),并收养该种动物中最早进入收容所的。
给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。若第一个元素为1,则代表有动物进入收容所,
第二个元素为动物的编号,正数代表狗,负数代表猫;若第一个元素为2,则代表有人收养动物,第二个元素若为0,则采取第一种收养方式,
若为1,则指定收养狗,若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作,即没有可以符合领养要求的动物,则将这次领养操作忽略。
测试样例:
[[1,1],[1,-1],[2,0],[2,-1]]
返回:[1,-1]

* \问题分析:
思路:定义两个vector<int>对象A和B,分别用于存放收容所里的动物和被收养的动物
操作如下:
对ope数组从按行从i = 0 ~ ope.size() -1遍历
1、指令为1(ope[i][0] = 1)时,即有动物进来,则将动物序号压入A--执行A.push_back(ope[i][1]);
2、指令为2(ope[i][0] = 2)时,即有动物被收养,此时首先判断A是否为空,即是否有动物
1)如果A为空,则continue
2)如果A不为空
1.如果操作为ope[i][1] = 0,即收养最先进来的动物,则将A[0]压入B,执行B.push_back(A[0]),然后在A中删除对应元素,即执行A.erase(A.begin());
2.如果操作为ope[i][1] = 1,即收养最先进来的狗,此时遍历A找到第一个狗,然后将找到的元素压入B,再在A中删除对应元素;
3.如果操作为ope[i][1] = -1,即收养最先进来的猫,此时遍历A找到第一个猫,然后将找到的元素压入B,再在A中删除对应的元素。
遍历完成之后,返回B。


*****************************************************/
#include <iostream>
using namespace std;
#include <vector>
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        int len = ope.size();
        vector<int> ans, in;
        if (len==0)
        {
            return ans;
        }
        for (int i = 0; i < len;i++)
        {
            if (ope[i][0]==1)  //有动物来收容所
            {
                in.push_back(ope[i][1]);
            }
            else if (ope[i][0]==2)  //    有人收养
            {
                if (in.empty())
                {
                    continue;
                }
                if (ope[i][1]==0)  //第一种收养方式,取第一个
                {
                    ans.push_back(in[0]);
                    in.erase(in.begin());
                }
                else if (ope[i][1]==1)  //指定养狗
                {
                    for (int i = 0; i < in.size();i++)
                    {
                        if (in[i]>0)
                        {
                            ans.push_back(in[i]);
                            in.erase(in.begin()+i);
                            break;
                        }
                    }
                }else if (ope[i][1]==-1) //指定养猫
                {
                    for (int i = 0; i < in.size();i++)
                    {
                        if (in[i]<0)
                        {
                            ans.push_back(in[i]);
                            in.erase(in.begin()+i);
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }
};


//////////////////////////////////////////////////////////////////////////
//题目分析:
//根据先进先出的原则,自然想到了用队列实现,如果只维护一个队列,那么第一种方法实现起来比较简单,只需要取出队头的动物则可以,
//但是第二种方法就比较复杂,需要访问整个队列来找出第一个被访问的猫或者狗。

//因此我们可以选择维护两个队列来实现,一个队列存放放入的狗,一个队列存放放入的猫,对于第二种方法实现起来相当容易,
//我们只需要根据要选择的猫或者狗从相应的队列中取出便可以,但是第一种方法需要判断那个两个队列头部的是猫先进入收容所,还是狗先进入,
//这个时候需要一个标志,所以我们每次把动物放入队列的时候,同时将一个递增的序号放入队列,这个序号就是一个时间序列,根据这个序号便可以轻松实现第一种方法。
//《程序员面试金典》--题目详解:
//http ://blog.csdn.net/zdplife/article/category/5799903
//////////////////////////////////////////////////////////////////////
#include <queue>
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())  //dog不为空
                        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;
    }
};

 

本文转载自:http://www.cnblogs.com/ranjiewen/p/5901228.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
动物收容所,先进先出

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

一贱书生
2016/11/17
52
0
带上萌宠去上班 | IT办公室宠物报告

专栏 | 九章算法 网址 | www.jiuzhang.com 1. Google(美国) 谷歌的公司行为守则上写着:对犬类的喜爱是谷歌企业文化的重要部分。 更有趣的是,谷歌公司对猫咪也非常友好,只是公司里有太多...

九章算法
03/28
0
0
java 接口(interface)的意义

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

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

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

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

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

Adairs
2016/03/10
35
0

没有更多内容

加载失败,请刷新页面

加载更多

Vue学习01

我的github地址https://github.com/zhangl-w/VueDemo/tree/master/VueDemo 一、基本代码 1.导入Vue包,导包后浏览器内存中会产生一个Vue的构造函数 2.创建一个Vue实例 3.el 表示,当前我们n...

zhang_l
29分钟前
5
0
centos7.x 安装harbor 1.9.3

首先必须安装docker和docker-compose 推荐使用pip安装docker-compose,因为pip可以为你自动对应版本问题 1.docker安装 curl -sfL https://get.docker.io | sh -systemctl start docker 2.d...

Elson
30分钟前
5
0
每天积累一点:射频阻抗

对我来说,阻抗是一个非常令人困惑的概念(术语)。以下是我第一次学习阻抗概念时脑海中出现的许多问题。同样的问题也让你烦恼吗? 当我第一次在高中物理中学习“电阻(Resistance )”时,它...

demyar
31分钟前
5
0
人生苦短?试试Groovy进行单元测试

如果您今天正在编程,那么您很可能听说过单元测试或测试驱动的开发过程。我还没有遇到一个既没有听说过又没有听说过单元测试并不重要的程序员。在随意的讨论中,大多数程序员似乎认为单元测试...

八音弦
32分钟前
4
0
GMAT词汇怎么背?简单记忆法让你不再害怕背单词

GMAT考试对于词汇的掌握和使用要求高,可以说是GMAT考试的难关之一。面对学术化专业化难度颇高的词汇,考生难免会产生畏惧退缩的情绪。GMAT难词怎么背?有没有轻松背单词的方法呢?下面小编就为...

bole6
34分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部