题解 | #三色球#

题目描述
有红、黄、蓝三种颜色的气球。
在牛客王国，1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票。
2个红气球+1个黄气球可以兑换1个蓝气球。
2个黄气球+1个蓝气球可以兑换1个红气球。
2个蓝气球+1个红气球可以兑换1个黄气球。
现在牛牛有a个红气球，b个黄气球， c个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。

方法一：暴力求解

求解思路
对于本题目的求解，我们首先找到三种气球中数量最少的那个，然后进行兑换彩票。这样数量最少的气球现在变成了0个，然后我们对其他的颜色进行气球兑换，这样依次重复上述操作即可得到本问题的解答。

图片说明

解题代码

class Solution {
public:
    int  change(int m, int n)
    {
        int mycount = 0; // 存储彩票的张数
        while (m > 0 && n > 0)
        {
            m -= 3; // 对气球数目进行更新
            n -= 2;
            if(m >= 0 && n >= 0)
            {
                mycount++;
            }
        }
        return mycount; // 返回数量
    }
    int solve(int a, int b, int c) {
        int mycount = min(a,min(b,c));
        a -= mycount; // 红气球
        b -= mycount; // 黄气球
        c -= mycount; // 蓝气球
        if(a == 0)
        {
            return mycount + change(b,c); // 更新结果
        }
        else if (b == 0)
        {
            return mycount  + change(c,a);
        }
        else
        {
            return mycount + change(a,b);
        }
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：常数级空间，因此空间复杂度为 $O(1)$

方法二：优化思想求解

求解思路
基于方法一，我们发现本题目可以通过三种情况求解出答案，具体操作方法代码展示。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int a, int b, int c)
    {
        int min = Math.min(a, Math.min(b, c)); // 存储最小值
        int myticket = min; // 存储彩票数目
        a -= min; // 红气球
        b -= min; // 黄气球
        c -= min; // 蓝气球
        if(a == 0)
        {   //case 1
            return myticket += Math.min(b/3, c/2); // 2黄+1蓝换1红
        }
        if(b == 0)
        {   //case 2
            return myticket += Math.min(c/3, a/2); // 2蓝+1红换1黄
        }
        if(c == 0)
        {   //case 3
            return myticket += Math.min(a/3, b/2); // 2红+1黄换1蓝
        }
        return myticket; // 返回彩票数目
    }
}

复杂度分析
时间复杂度：常数级时间，因此时间复杂度为 $O(1)$
空间复杂度：常数级空间，因此空间复杂度为 $O(1)$