LeetCode 题解工作台
得到新鲜甜甜圈的最多组数
有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
题目实际上要我们找到一种安排顺序，使得前缀和（这里指的是“人数”）与 取模后为 的组数最多。因此，我们可以将所有顾客按组分成两类： - 人数为 的整数倍的顾客，这些顾客不会对下一组顾客的甜甜圈产生影响，我们可以贪心地优先安排这些组的顾客，那么这些组的顾客都会感到开心，“初始答案”为这些组的数量；
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。
当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。
你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。
示例 1：
输入：batchSize = 3, groups = [1,2,3,4,5,6] 输出：4 解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。
示例 2：
输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6] 输出：4
提示：
1 <= batchSize <= 91 <= groups.length <= 301 <= groups[i] <= 109
解题思路
方法一：贪心 + 状态压缩 + 记忆化搜索
题目实际上要我们找到一种安排顺序，使得前缀和（这里指的是“人数”）与 取模后为 的组数最多。因此，我们可以将所有顾客按组分成两类：
- 人数为 的整数倍的顾客，这些顾客不会对下一组顾客的甜甜圈产生影响，我们可以贪心地优先安排这些组的顾客，那么这些组的顾客都会感到开心，“初始答案”为这些组的数量；
- 人数不为 的整数倍的顾客，这些顾客的安排顺序会影响下一组顾客的甜甜圈。我们可以对这里每一组的人数 模 ，得到的这些余数构成一个集合，集合中的元素值范围是 。数组 的长度最大为 ，因此，每个余数的数量最大不超过 。我们可以用 个二进制位来表示一个余数的数量，而 最大为 ，那么表示这些余数以及对应的数量总共需要的二进制位就是 。我们可以用一个 位整数 来表示。
接下来，我们设计一个函数 ，表示安排状态为 ，且当前前缀余数为 时，能使得多少组感到开心。那么我们在“初始答案”加上 ，即为最终答案。
函数 的实现逻辑如下：
我们枚举 到 的每一个余数 ，如果余数 的数量不为 ，那么我们可以将余数 的数量减去 ，将当前前缀余数加上 并且对 取模，然后递归调用函数 ，求出子状态的最优解，取最大值即可。最后判断 是否为 ，如果为 ，我们在最大值上加 后返回，否则直接返回最大值。
过程中，我们可以使用记忆化搜索来避免状态的重复计算。
时间复杂度不超过 ，空间复杂度不超过 。
class Solution:
def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
@cache
def dfs(state, mod):
res = 0
x = int(mod == 0)
for i in range(1, batchSize):
if state >> (i * 5) & 31:
t = dfs(state - (1 << (i * 5)), (mod + i) % batchSize)
res = max(res, t + x)
return res
state = ans = 0
for v in groups:
i = v % batchSize
ans += i == 0
if i:
state += 1 << (i * 5)
ans += dfs(state, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is roughly O(batchSize^groups.length) due to all possible state combinations, reduced with memoization and pruning. Space complexity is O(batchSize^groups.length) for memoization storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Noticing that direct permutation is infeasible due to group length.
- question_mark
Observing that happy groups depend on sum modulo batchSize.
- question_mark
Asking for dynamic programming optimization using remainders.
常见陷阱
外企场景- error
Forgetting that only the first customer in a batch affects happiness.
- error
Neglecting groups that are multiples of batchSize which are immediately happy.
- error
Failing to memoize states leading to TLE on larger inputs.
进阶变体
外企场景- arrow_right_alt
Maximize happy groups with variable batch sizes per day.
- arrow_right_alt
Compute minimum leftover donuts while maximizing happy groups.
- arrow_right_alt
Adapt the solution to include group-specific donut preferences affecting happiness.