面试18之猫狗队列

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

返回：[1,-1]

方法一：

用一个vector来表示收养所，数组的头部元素就是最早进入收留所的动物，遍历一遍，找到第一个大于0的编号就是狗，第一个小于0的编号就是猫，
这种方式简单，但是效率低，每出一个动物都得遍历一遍，时间复杂度为O（N*N)。

vector<int> Asylum(vector<vector<int> > ope)
{

	vector<int> A;  //表示收养所
	vector<int> B;  //表示被收养的动物。

	for(int i = 0; i < ope.size(); ++i)
	{
		if(ope[i][0] == 1) //表示动物进收留所。
		{
				A.push_back(ope[i][1]); //将动物的编号放入收养所。  
		}

		if(ope[i][0] == 2) //表示有人收养动物了。
		{
			if(A.empty()) //如果收养所没有动物能收养，自己结束这次操作。
				continue;
			if(ope[i][1] == 0)  //第一种方式收养。收养的是最早进入收留所的动物。
			{
				B.push_back(A[0]);
				//收留所 要清除最早的动物。
				A.erase(A.begin());  
			}
			if(ope[i][1] == 1) //收养最早的狗。狗的编号大于0
			{	
				for(int j = 0; j < A.size(); ++j)
				{
					if(A[j] > 0) //找到最早的狗
					{
						B.push_back(A[j]);
						A.erase(A.begin()+j);
						break;
					}
				}
			}
			if(ope[i][1] == -1) //收养最早的猫。
			{
				for(int j = 0; j < A.size(); ++j)
				{
					if(A[j] < 0) //找到最早的猫，猫的编号小于0.
					{
						B.push_back(A[j]);
						A.erase(A.begin()+j);
						break;
					}
				}
			
			}
		}
	}
	return B;
}

vector<int> Asylum(vector<vector<int> > ope)
{
	queue<int> cat;
	queue<int> dog;
	vector<int> ret;
	int idx = 0;  //表示时间。
	for(int i = 0; i < ope.size(); ++i)
	{
		if(ope[i][0] == 1) //有动物要进收养所了。
		{
			if(ope[i][1] > 0) //编号大于0，表示狗进入
			{
				dog.push(idx++); //把动物的时序也一并压入。
				dog.push(ope[i][1]);
			}
			else
			{
				cat.push(idx++);
				cat.push(ope[i][1]);
			}
		}
		if(ope[i][0] == 2) //表示有人要收养动物了。
		{
			if(ope[i][1] == 0) //第一种方式收养，收养最早的动物。
			{
				int catidx = cat.empty() ? 10000000 :cat.front(); 
				int dogidx = dog.empty() ? 10000000 :dog.front();
				if(catidx < dogidx)
				{
					cat.pop(); //把时序弹出。
					ret.push_back(cat.front() );
					cat.pop();
				}
				else
				{
					dog.pop(); //把时序弹出。
					ret.push_back(dog.front() );
					dog.pop();
				}
			}
			else if(ope[i][1] == 1) //第二种方式收养，收养狗
			{
				if(!dog.empty())
				{
					dog.pop(); //把时序弹出。
					ret.push_back(dog.front() );
					dog.pop();
				}
			}
			else
			{
				if(!cat.empty() )
				{
					cat.pop(); //把时序弹出。
					ret.push_back(cat.front() );
					cat.pop();
				}
			}
			
		}
	}
	return ret;
}

void test()
{
	vector<int > v[4];
	v[0].push_back(1);
	v[0].push_back(1);
	v[1].push_back(1);
	v[1].push_back(-1);
	v[2].push_back(2);
	v[2].push_back(0);
	v[3].push_back(2);
	v[3].push_back(-1);
	
	vector<vector<int> > vv;
	for(int i = 0; i < 4; ++i)
	{
		vv.push_back(v[i]);
	}

	vector<int> ret = Asylum(vv);

	for(int i = 0; i < ret.size(); ++i)
	{
		cout << ret[i] << " ";
	}
	cout <<endl;
}


int main()
{

	test();

	cout << "hello..."<<endl;

	return 0;
}

最后

以上就是如意小兔子为你收集整理的面试18之猫狗队列的全部内容，希望文章能够帮你解决面试18之猫狗队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。