题解 | #三色球#
三色球
http://www.nowcoder.com/practice/57328decf4734bdb8d8b68a324640806
三色球
问题描述：有红、黄、蓝三种颜色的气球。在牛客王国，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，此时分为三种情况如下：
- 如果蓝气球数为0，则使用3个红气球+2个黄气球兑换一张彩票，彩票数为min(a/3，b/2)；
- 如果红气球数为0，则使用3个黄气球+2个蓝气球兑换一张彩票，彩票数为min(b/3，c/2)；
- 如果黄气球数为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)$
