LeetCode 题解工作台
分配重复整数
给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足： 第 i 位顾客 恰好 有 quantity[i…
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们先统计数组 中每个数字出现的次数，记录在哈希表 中，然后将哈希表中的值存入数组 中，我们记数组 的长度为 。 注意到数组 的长度不超过 ，因此，我们可以用一个二进制数表示 中的一个子集，即数字 表示 中的一个子集，其中 的二进制表示中的第 位为 表示 中的第 个数字被选中，为 表示第 个数字未被选中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：
- 第
i位顾客 恰好 有quantity[i]个整数。 - 第
i位顾客拿到的整数都是 相同的 。 - 每位顾客都满足上述两个要求。
如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。
示例 1：
输入：nums = [1,2,3,4], quantity = [2] 输出：false 解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：
输入：nums = [1,2,3,3], quantity = [2] 输出：true 解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：
输入：nums = [1,1,2,2], quantity = [2,2] 输出：true 解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 105nums中至多有50个不同的数字。
解题思路
方法一：状态压缩动态规划 + 子集枚举
我们先统计数组 中每个数字出现的次数，记录在哈希表 中，然后将哈希表中的值存入数组 中，我们记数组 的长度为 。
注意到数组 的长度不超过 ，因此，我们可以用一个二进制数表示 中的一个子集，即数字 表示 中的一个子集，其中 的二进制表示中的第 位为 表示 中的第 个数字被选中，为 表示第 个数字未被选中。
我们可以预处理出数组 ，其中 表示 中子集 中所有数字的和。
接下来，我们定义 表示数组 中的数字能否成功分配给 中的子集 ，其中 的取值范围为 ，而 的取值范围为 ，其中 为 的长度。
考虑 ，如果子集 中存在一个子集 ，使得 ，并且 为真，那么 为真，否则 为假。
答案为 。
时间复杂度 ，空间复杂度 。其中 是数组 中不同整数的个数；而 是数组 的长度。
class Solution:
def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
m = len(quantity)
s = [0] * (1 << m)
for i in range(1, 1 << m):
for j in range(m):
if i >> j & 1:
s[i] = s[i ^ (1 << j)] + quantity[j]
break
cnt = Counter(nums)
arr = list(cnt.values())
n = len(arr)
f = [[False] * (1 << m) for _ in range(n)]
for i in range(n):
f[i][0] = True
for i, x in enumerate(arr):
for j in range(1, 1 << m):
if i and f[i - 1][j]:
f[i][j] = True
continue
k = j
while k:
ok1 = j == k if i == 0 else f[i - 1][j ^ k]
ok2 = s[k] <= x
if ok1 and ok2:
f[i][j] = True
break
k = (k - 1) & j
return f[-1][-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of unique numbers and customer orders, roughly O(2^m * n) in the worst case due to all DP states. Space complexity is O(2^m) for storing DP states. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Counting frequencies before attempting assignment indicates understanding of data reduction for DP.
- question_mark
Implementing bitmask DP shows awareness of handling subsets efficiently in state transition problems.
- question_mark
Pruning impossible paths during backtracking signals optimization for hard cases with repeated numbers.
常见陷阱
外企场景- error
Failing to account for identical numbers and giving a customer distinct integers instead.
- error
Overlooking pruning opportunities, leading to TLE for larger frequency distributions.
- error
Incorrectly initializing DP states, causing invalid assignments to propagate.
进阶变体
外企场景- arrow_right_alt
Distribute integers allowing each customer to receive either one or two identical numbers.
- arrow_right_alt
Maximize the number of customers satisfied given limited repeated integers in nums.
- arrow_right_alt
Distribute integers with constraints on specific integer types per customer.