Medium
题目描述
给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料如下：
- 巨无霸汉堡：4 片番茄和 1 片奶酪
- 小皇堡：2 片番茄和 1 片奶酪
请你以 [total_jumbo, total_small] 的格式返回恰当的制作方案，使得剩余的番茄片数和奶酪片数都是 0。如果无法使剩余的番茄片和奶酪片都等于 0，就请返回 []。
示例 1：
输入：tomatoSlices = 16, cheeseSlices = 7
输出：[1,6]
解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 4*1 + 2*6 = 16 个番茄和 1 + 6 = 7 个奶酪。不会剩下原料。
示例 2：
输入：tomatoSlices = 17, cheeseSlices = 4
输出：[]
解释：无法使用所有原料制作巨无霸汉堡和小皇堡。
示例 3：
输入：tomatoSlices = 4, cheeseSlices = 17
输出：[]
解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。
约束条件：
0 <= tomatoSlices, cheeseSlices <= 10^7
解题思路
这是一个典型的二元一次方程组求解问题。
设巨无霸汉堡数量为 x，小皇堡数量为 y，根据题意可以建立方程组：
- 4x + 2y = tomatoSlices（番茄片约束）
- x + y = cheeseSlices（奶酪片约束）
从第二个方程得到：y = cheeseSlices - x
代入第一个方程：4x + 2(cheeseSlices - x) = tomatoSlices
化简得：4x + 2cheeseSlices - 2x = tomatoSlices 即：2x = tomatoSlices - 2cheeseSlices 所以：x = (tomatoSlices - 2*cheeseSlices) / 2
相应地：y = cheeseSlices - x = (2*cheeseSlices - tomatoSlices) / 2
为了保证解的有效性，需要满足以下条件：
- x 和 y 都必须是非负整数
- tomatoSlices - 2*cheeseSlices 必须是偶数（保证 x 为整数）
- x ≥ 0 且 y ≥ 0
这种数学解法时间复杂度为 O(1)，是最优解。
代码实现
class Solution {
public:
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
// 检查番茄片数是否为偶数（必要条件）
if (tomatoSlices % 2 != 0) {
return {};
}
// 计算巨无霸汉堡和小皇堡的数量
int jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
int small = cheeseSlices - jumbo;
// 检查解的有效性
if (jumbo >= 0 && small >= 0) {
return {jumbo, small};
}
return {};
}
};
class Solution:
def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
# 检查番茄片数是否为偶数（必要条件）
if tomatoSlices % 2 != 0:
return []
# 计算巨无霸汉堡和小皇堡的数量
jumbo = (tomatoSlices - 2 * cheeseSlices) // 2
small = cheeseSlices - jumbo
# 检查解的有效性
if jumbo >= 0 and small >= 0:
return [jumbo, small]
return []
public class Solution {
public IList<int> NumOfBurgers(int tomatoSlices, int cheeseSlices) {
// 检查番茄片数是否为偶数（必要条件）
if (tomatoSlices % 2 != 0) {
return new List<int>();
}
// 计算巨无霸汉堡和小皇堡的数量
int jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
int small = cheeseSlices - jumbo;
// 检查解的有效性
if (jumbo >= 0 && small >= 0) {
return new List<int> { jumbo, small };
}
return new List<int>();
}
}
var numOfBurgers = function(tomatoSlices, cheeseSlices) {
// 检查番茄片数是否为偶数（必要条件）
if (tomatoSlices % 2 !== 0) {
return [];
}
// 计算巨无霸汉堡和小皇堡的数量
const jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
const small = cheeseSlices - jumbo;
// 检查解的有效性
if (jumbo >= 0 && small >= 0) {
return [jumbo, small];
}
return [];
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |