三色球

问题描述：有红、黄、蓝三种颜色的气球。在牛客王国，1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票。
2个红气球+1个黄气球可以兑换1个蓝气球。
2个黄气球+1个蓝气球可以兑换1个红气球。
2个蓝气球+1个红气球可以兑换1个黄气球。
现在牛牛有a个红气球，b个黄气球， c个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。
示例
输入：1,7,5
返回值：3
说明：可以用4个黄气球和2个蓝气球换2个红气球，这样就有了3个红气球，3个黄气球，3个蓝气球，可以换3个彩票。

方法一

思路分析

      首先找到三种气球中数量最小的那一种，表示直接兑换彩票的数量，那么接下来必然会存在有一种颜色的气球数量为0，那么需要对剩下的气球先兑换不存在的气球，然后兑换彩票，将这一过程包装在一个函数中，不断的循环判断可以兑换的次数，即表示彩票数量，即存在下面三种情况：
  • 如果蓝气球数为0，则使用3个红气球+2个黄气球兑换一张彩票，在条件下，循环的次数，次数即为兑换彩票的张数；
  • 如果红气球数为0，则使用3个黄气球+2个蓝气球兑换一张彩票，在条件下，循环的次数，次数即为兑换彩票的张数；
  • 如果黄气球数为0，则使用3个蓝气球+2个红气球兑换一张彩票，在条件下，循环的次数，次数即为兑换彩票的张数；

C++核心代码 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 三色球
     * @param a int整型 
     * @param b int整型 
     * @param c int整型 
     * @return int整型
     */
    int  change(int m, int n){
        int count = 0;
        while (m > 0 && n > 0){
            m -= 3;//2个黄气球+1个蓝气球可以兑换1个红气球或者2个蓝气球+1个红气球可以兑换1个黄气球或者2个红气球+1个黄气球可以兑换1个蓝气球。
            n -= 2;
            if(m >= 0 && n >= 0){
                count++;
            }
        }
        return count;
    }
    int solve(int a, int b, int c) {
        // write code here
         int count = min(a,min(b,c));
        a -= count;//剩余的红气球
        b -= count;//剩余的黄气球
        c -= count;//剩余的蓝气球
        if(a == 0){
            return count + change(b,c);//红气球为0
        }else if (b == 0){
            return count  + change(c,a);//黄气球为0
        }else {
            return count + change(a,b);//蓝气球为0
        }
    }
};

复杂度分析

  • 时间复杂度：当一种颜色的气球数量为0时，需要进行兑换，兑换的时间复杂度主要产生于剩余气球的数量，因此时间复杂度为$O(max(a,b,c))$
  • 空间复杂度：常数空间，空间复杂度为$O(1)$

方法二

思路分析

题目中给定兑换方案如下：
  • 1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票，首先找到三种气球中数量最小的那一种，表示直接兑换彩票的数量
  • 2个红气球+1个黄气球可以兑换1个蓝气球，那么使用3个红气球+2个黄气球可以兑换一张彩票
  • 2个黄气球+1个蓝气球可以兑换1个红气球，那么使用3个黄气球+2个蓝气球可以兑换一张彩票
  • 2个蓝气球+1个红气球可以兑换1个黄气球，那么使用3个蓝气球+2个红气球可以兑换一张彩票

具体过程如下：

  • m=min(a,b,c)表示直接兑换彩票的数量，三种气球中数量最小的那一种，表示直接兑换彩票的数量
  • 更新兑换后的各颜色的气球数量
  • 此时必然会存在一种气球的数量为0，此时分为三种情况如下：
  1. 如果蓝气球数为0，则使用3个红气球+2个黄气球兑换一张彩票，彩票数为min(a/3，b/2)；
  2. 如果红气球数为0，则使用3个黄气球+2个蓝气球兑换一张彩票，彩票数为min(b/3，c/2)；
  3. 如果黄气球数为0，则使用3个蓝气球+2个红气球兑换一张彩票，彩票数为min(c/3，a/2)；

图解




Java核心代码 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 三色球
     * @param a int整型 
     * @param b int整型 
     * @param c int整型 
     * @return int整型
     */
    public int solve (int a, int b, int c) {
        // write code here
        int min = Math.min(a, Math.min(b, c));//1个红气球+1个黄气球+1个蓝气球可以兑换彩票数
        int ticket = min;
        a -= min;//剩余的红气球
        b -= min;//剩余的黄气球
        c -= min;//剩余的蓝气球
        if(a == 0){
            return ticket += Math.min(b/3, c/2);//2个黄气球+1个蓝气球可以兑换1个红气球
        }
        if(b == 0){
            return ticket += Math.min(c/3, a/2);//2个蓝气球+1个红气球可以兑换1个黄气球
        }
        if(c == 0){
            return ticket += Math.min(a/3, b/2);//2个红气球+1个黄气球可以兑换1个蓝气球。
        }
        return ticket;
    }
}

复杂度分析

  • 时间复杂度：常数时间，时间复杂度为$O(1)$
  • 空间复杂度：常数空间，空间复杂度为$O(1)$