首页 > 试题广场 >

分条件出栈

[编程题]分条件出栈
  • 热度指数:18677 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个栈及一个操作序列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。
代码如下所示:
class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        vector<int> A;   //定义动物序列
        vector<int> B;   //定义收养序列
        int i;     //定义循环变量
        int len = ope.size();
        for(i = 0; i < len; i ++)
            {
            if(ope[i][0] == 1) //有动物进来
                A.push_back(ope[i][1]);  //放入动物序列
            else
                if(A.empty())
                 continue;
                else
                 if(ope[i][1] == 0)  //第一种收养方式
                  {
                     B.push_back(A[0]);
                     A.erase(A.begin()); //从A中删除对应元素
                 }
              else
                     if(ope[i][1] == 1)  //收养狗
                     {
                         for(int j = 0; j < A.size(); j ++)
                       if(A[j] > 0)
                       {
                        B.push_back(A[j]);
                        A.erase(A.begin() + j); //从A中删除对应元素
                        break;
                    }
                     }
               else
                            for(int j = 0; j < A.size(); j ++)
                       if(A[j] < 0)
                       {
                        B.push_back(A[j]);
                        A.erase(A.begin() + j); //从A中删除对应元素
                        break;
                    }
        }
        return B;
    }
};
          
编辑于 2015-08-18 20:08:14 回复(4)