难度: Easy
Submission
运行时间: 149 ms
内存: 31.0 MB
class Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: ans = 0 arr = [0 for i in range(x+1)] for sta in staple: if sta < x: arr[sta] += 1 for i in range(2, x): arr[i] += arr[i-1] for drink in drinks: lt = x - drink if lt <= 0: continue ans += arr[lt] return ans % (10 ** 9 + 7)
Explain
这个题解采用了前缀和的思想加上一点优化来减少查找时间。首先,创建一个长度为x+1的数组arr,用于记录每个价格以下的主食数量。遍历主食数组staple,对于每个价格小于x的主食,增加arr中对应价格索引的计数。然后,对arr数组进行前缀和处理,使得arr[i]表示所有价格小于等于i的主食总数。接着,遍历饮料数组drinks,对每种饮料,计算其与主食组合的最大可接受价格x-drink。如果这个值大于0,那么直接从arr数组中得到所有价格小于等于这个值的主食数量,加到答案中。最后,由于可能出现计数非常大的情况,对最终结果取模1e9+7。
时间复杂度: O(n + m + x)
空间复杂度: O(x)
class Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: ans = 0 arr = [0 for i in range(x+1)] # 创建长度为x+1的数组,初始化为0 for sta in staple: if sta < x: arr[sta] += 1 # 记录每个价格的主食数量 for i in range(2, x): arr[i] += arr[i-1] # 计算价格的前缀和 for drink in drinks: lt = x - drink if lt <= 0: continue ans += arr[lt] # 对于每种饮料,计算可搭配的主食方案数 return ans % (10 ** 9 + 7) # 结果取模1e9+7
Explore
在计算前缀和时,起始索引从2开始是由于算法中的逻辑错误或者是代码实现上的疏忽。正确的实现应该是从索引1开始计算前缀和,因为索引1代表价格为1的主食数量,这也意味着需要累加从价格1开始的所有主食数量。从2开始会导致忽略了价格为1的主食数量在前缀和中的累加,这是不正确的。应该从1开始,确保所有有效价格的主食都被正确计算在内。
当lt(x-drink)的值小于等于0时,这意味着饮料的价格已经超过了组合的预算上限x。在代码中这种情况会被直接跳过(continue语句),因此不会对总方案数产生任何贡献。这是一种有效的处理方法,因为任何超出预算的饮料都不能与任何主食形成有效的价格组合,所以这些情况应当被排除在外。
是的,在实现中如果主食的价格超过了x,那么这个主食价格不会被记录在arr数组中,意味着它不会被考虑在内。这种处理是合理的,因为如果主食的价格本身已经超出了整体预算x,那么无论如何搭配饮料,这种组合的总价格都会超出x,不可能成为一个有效的选项。因此,忽略这些超出预算的主食是正确和必要的。