LeetCode 1276. Number of Burgers

@(LeetCode)

问题描述

给定两个整数：tomatoSlices 和 cheeseSlices。其中 tomatoSlices 代表西红柿片数， cheeseSlices 代表奶酪片数。

不同汉堡所需要的配料如下：

• 巨无霸汉堡：4 片西红柿 + 1 片奶酪
• 小汉堡：2 片西红柿 + 1 片奶酪

要求返回数组 [巨无霸汉堡的数量, 小汉堡的数量]，使得剩余的西红柿片和奶酪片数量都为 0。如果不能满足条件，则返回空数组 []。

栗 1：

输入: tomatoSlices = 16, cheeseSlices = 7
输出: [1,6]
解释：西红柿片数 = 1 * 4 + 2 * 6 = 16，奶酪片数= 1 + 6 = 7

栗 2：

输入: tomatoSlices = 17, cheeseSlices = 4
输出: []
解释：无法用完所有配料来做成汉堡。

栗 3：

输入: tomatoSlices = 4, cheeseSlices = 17
输出: []
解释：无法用完所有配料来做成汉堡。

栗 4：

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

栗 5：

输入: tomatoSlices = 2, cheeseSlices = 1
输出: [0,1]
解释：西红柿片数 = 0 * 4 + 2 * 1 = 2，奶酪片数= 0 + 1 = 1

注意：

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

想看英文原文的戳这里。

解题思路

这道题比较简单，其实就是数学题，列出方程式，求解即可。

假设巨无霸汉堡个数为 x，小汉堡个数为 y，则它们满足如下公式：

4x + 2y = tomatoSlices
x + y = cheeseSlices

消除 y，变为：

2x = tomatoSlices - 2 * cheeseSlices

进一步得出：

x = tomatoSlices/2 - cheeseSlices

这样就求出了 x。y 的值就好办了，y = cheeseSlices - x 即可。

但其还存在一些隐性条件：

• tomatoSlices 需为偶数
• tomatoSlices/2 - cheeseSlices >= 0

代码也挺简单的，js 代码如下：

/**
 * @param {number} tomatoSlices
 * @param {number} cheeseSlices
 * @return {number[]}
 */
var numOfBurgers = function(tomatoSlices, cheeseSlices) {
    if (tomatoSlices % 2 === 0) {
        const numberOfBig = tomatoSlices/2 - cheeseSlices
        if (numberOfBig >= 0) {
            const numberOfSmall = cheeseSlices - numberOfBig
            if (numberOfSmall >= 0) {
                return [numberOfBig, numberOfSmall]
            }
        }
    }

    return []
};

注意：不要陷入穷举法的怪圈，因为数量级很大。

以上代码可查看 数学解法。