不浪费原料的汉堡制作方案

难度: Medium

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。

给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：

巨无霸汉堡：4 片番茄和 1 片奶酪
小皇堡：2 片番茄和 1 片奶酪

请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。

如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 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 片奶酪。

示例 4：

输入：tomatoSlices = 0, cheeseSlices = 0
输出：[0,0]

示例 5：

输入：tomatoSlices = 2, cheeseSlices = 1
输出：[0,1]

提示：

0 <= tomatoSlices <= 10^7
0 <= cheeseSlices <= 10^7

Submission

运行时间: 24 ms

内存: 16.7 MB

class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
        k = 4*cheeseSlices - tomatoSlices
        total_jumbo = k//2
        total_small = cheeseSlices - total_jumbo
        return [] if k % 2 or total_jumbo < 0 or total_small < 0 else [total_small,total_jumbo]

Explain

首先，通过设置两个方程来表示番茄片和奶酪片的使用情况： - 4 * total_jumbo + 2 * total_small = tomatoSlices - total_jumbo + total_small = cheeseSlices 将第二个方程解为 total_jumbo = cheeseSlices - total_small，代入第一个方程，我们可以得到一个只有一个未知数（total_small）的方程。通过解这个方程，我们可以求出 total_small 的值，再代回求 total_jumbo。为了解这个方程，我们首先将 total_jumbo 用 cheeseSlices 表达，得到： - 4 * (cheeseSlices - total_small) + 2 * total_small = tomatoSlices - 4 * cheeseSlices - 4 * total_small + 2 * total_small = tomatoSlices - 2 * cheeseSlices - 2 * total_small = tomatoSlices 从中解出 total_small，如果得到的解是整数且满足 total_small 和 total_jumbo 都非负，则返回这些值。否则返回空数组表示没有可行解。

时间复杂度: O(1)

空间复杂度: O(1)

# 定义类和方法
class Solution:
    def numOfBurgers(self, tomatoSlices: int, cheeseSlices: int) -> List[int]:
        # 计算需要解决的方程差值
        k = 4*cheeseSlices - tomatoSlices
        # 解出巨无霸汉堡的数量
        total_jumbo = k//2
        # 解出小皇堡的数量
        total_small = cheeseSlices - total_jumbo
        # 检查解是否为整数且汉堡数量非负
        return [] if k % 2 or total_jumbo < 0 or total_small < 0 else [total_small,total_jumbo]

Explore

原问题给出了制作两种类型汉堡所需的番茄片和奶酪片的数量。通过分析，每个巨无霸汉堡需要4片番茄和1片奶酪，每个小皇堡需要2片番茄和1片奶酪。这种每种资源与汉堡数量的关系形成了线性关系，因此可以通过设立两个方程来表达这种资源消耗关系。第一个方程代表番茄片的总使用量，第二个方程代表奶酪片的总使用量。这样的线性方程组可以通过代数方法来求解，找出符合条件的汉堡数量组合。

题解中的验证步骤确实足够确保解出的 total_jumbo 和 total_small 都是非负整数。首先，题解中检查了 k % 2，确保从方程中解出的 total_jumbo 是整数（因为如果 k 不是偶数，则 total_jumbo 不会是整数）。其次，通过检查 total_jumbo < 0 或 total_small < 0 来确保所有解都是非负的。如果任何一个条件不满足，则返回空数组表示无解，这样的验证确保了解的有效性和问题的要求符合。

在方程 `4 * cheeseSlices - 4 * total_small + 2 * total_small = tomatoSlices` 中，我们可以通过合并同类项来简化这个方程。具体来说，-4 * total_small 和 +2 * total_small 合并得到 -2 * total_small。因此，方程简化为 `4 * cheeseSlices - 2 * total_small = tomatoSlices`。再将整个方程两边同时除以2，得到 `2 * cheeseSlices - total_small = tomatoSlices / 2`。因此，从原始方程直接推导出简化的方程。

选择将 total_jumbo 表达为 `cheeseSlices - total_small` 是因为这样的代换可以直接利用第二个方程 `total_jumbo + total_small = cheeseSlices`。这种代换使得将 total_jumbo 用 cheeseSlices 和 total_small 表示变得直接和简洁，从而可以更容易地将其代入第一个方程进行求解。如果选择将 total_small 表达为 `cheeseSlices - total_jumbo`，虽然同样可行，但在这种情况下，直接用 total_jumbo 代入可以更快地得到 total_small 的表达式和解，这有助于简化计算过程。