阿里巴巴笔试题

博客园链接 https://www.cnblogs.com/hustyan/p/12531879.html
阿里的笔试真的有点难，两道笔试题一个小时，感觉只能做出一道题来，笔试的时候也没做出来，结束了之后理清思路花了一小时才写好

1. 一副扑克牌，总共有 A 2 3 4 5 6 7 8 9 10 每张牌各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;
}