阿里巴巴 出扑克牌笔试题

阿里巴巴笔试题

阿里的笔试真的有点难，两道笔试题一个小时，感觉只能做出一道题来，笔试的时候也没做出来，结束了之后理清思路花了一小时才写好

1. 一副扑克牌，总共有 A 2 3 4 5 6 7 8 9 每张牌各4张，从中抽取任意张牌，牌可以有四种出法

   1. 单张牌，比如说 A
   2. 一对牌，比如说 两个2
   3. 五张牌顺子，比如说 A 2 3 4 5
   4. 六张牌连对，比如说 A A 2 2 3 3

   现在输入是10种牌每张牌的个数，如 1 1 1 2 2 2 2 2 1 1 ，指的是这10张牌每张的个数，现在问最少出几次能把牌出完。

   此时的解答是3次，出3个顺子可以达到目标。

   深度优先加回溯

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   int find6(vector<int> datas, int start, int& loc)
   {
   	if (start >= 8)
   		return 0;
   	int min = 10;
   	int times = 0;
   	for (int i = start; i < 10; i++)
   	{
   		if (datas[i] < min )	min = datas[i];
   		if (min < 2)
   		{
   			min = 10;
   			times = 0;
   		}
   		else
   		{
   			times++;
   			if (times == 3)
   			{
   				loc = i - 2;
   				if (min == 4)
   					return 2;
   				else
   					return 1;
   			}
   		}
   	}
   	return 0;
   }
   void sub6(vector<int>& datas, int loc, int times)
   {
   	datas[loc] -= 2*times;
   	datas[loc+1] -= 2*times;
   	datas[loc+2] -= 2*times;
   }
   
   void add6(vector<int>& datas, int loc) {
   	datas[loc] += 2;
   	datas[loc + 1] += 2;
   	datas[loc + 2] += 2;
   }
   
   int find5(vector<int> datas, int start, int& loc)
   {
   	if (start >= 6)
   		return 0;
   	int min = 10;
   	int times = 0;
   	for (int i = start; i < 10; i++)
   	{
   		if (datas[i] < min)	min = datas[i];
   		if (min == 0)
   		{
   			min = 10;
   			times = 0;
   		}
   		else
   		{
   			times++;
   			if (times == 5)
   			{
   				loc = i - 4;
   				return min;
   			}
   		}
   	}
   	return 0;
   }
   void sub5(vector<int>& datas, int loc,int times)
   {
   	datas[loc] -= times;
   	datas[loc + 1] -= times;
   	datas[loc + 2] -= times;
   	datas[loc + 3] -= times;
   	datas[loc + 4] -= times;
   }
   
   void add5(vector<int>& datas, int loc) {
   	datas[loc] += 1;
   	datas[loc + 1] += 1;
   	datas[loc + 2] += 1;
   	datas[loc + 3] += 1;
   	datas[loc + 4] += 1;
   }
   
   
   void dfs(vector<int>& datas, int& min, int cur, int step,int start)
   {
   	int loc = 0;
   	if (step == 0)
   	{
   		if (start >= 8)
   		{
   			dfs(datas,min, cur, 1, 0);
   		}
   		else
   		{
   			int nums = find6(datas, start, loc); //loc 是指的找到了并开始的地方
   			if (nums == 0)
   			{
   				dfs(datas, min, cur, 1, 0);
   			}
   			else
   			{
   				int n = nums;
   				sub6(datas, loc, nums);
   				while (n)
   				{
   					dfs(datas, min, cur + n, 0, loc + 1);
   					add6(datas, loc);
   					n--;
   				}
   				dfs(datas, min, cur, 0, loc + 3);
   			}
   		}
   	}
   	else if (step == 1)
   	{
   		if (start >= 6)
   		{
   			dfs(datas, min, cur, 2, 0);
   		}
   		else
   		{
   			int nums = find5(datas, start, loc); //loc 是指的找到了并开始的地方
   
   			if (nums == 0)
   			{
   				dfs(datas, min, cur, 2, 0);
   			}
   			else
   			{
   				int n = nums;
   				sub5(datas, loc, nums);
   				while (n)
   				{
   					dfs(datas, min, cur + n, 1, loc + 1);
   					add5(datas, loc);
   					n--;
   				}
   				dfs(datas, min, cur, 1, loc + 5);
   			}
   		}
   	}
   	else
   	{
   		int nums = 0;
   		for (int i = 0; i < 10; i++)
   		{
   			if (datas[i] > 0 && datas[i] <= 2)
   			{
   				nums++;
   			}
   			else if (datas[i] > 2 && datas[i] <= 4)
   			{
   				nums += 2;
   			}
   		}
   		cur += nums;
   		if (min > cur)
   			min = cur;
   	}
   }
   
   int main()
   {
   	vector<int>  datas(10);
   	for (int i = 0; i < 10; i++)
   	{
   		cin >> datas[i];
   	}
   	int min = 50;
   	dfs(datas,min,0,0,0);
   	cout << min;
   }