LeetCode 题解工作台
最小的必要团队
作为项目经理，你规划了一份需求的技能清单 req_skills ，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。 所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们注意到，技能清单 `req_skills` 的长度不超过 ，因此，我们可以用一个长度不超过 的二进制数来表示每一种技能是否被掌握。不妨记数组 `req_skills` 的长度为 ，数组 `people` 的长度为 。 我们先将 `req_skills` 中的每个技能映射到一个编号，即 表示技能 的编号。然后，我们遍历 `people` 中的每个人，将其掌握的技能用二进制数表示，即 表示…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
- 例如，团队
team = [0, 1, 3]表示掌握技能分别为people[0]，people[1]，和people[3]的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。
示例 1：
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]] 输出：[0,2]
示例 2：
输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]] 输出：[1,2]
提示：
1 <= req_skills.length <= 161 <= req_skills[i].length <= 16req_skills[i]由小写英文字母组成req_skills中的所有字符串 互不相同1 <= people.length <= 600 <= people[i].length <= 161 <= people[i][j].length <= 16people[i][j]由小写英文字母组成people[i]中的所有字符串 互不相同people[i]中的每个技能是req_skills中的技能- 题目数据保证「必要团队」一定存在
解题思路
方法一：状态压缩动态规划
我们注意到，技能清单 req_skills 的长度不超过 ，因此，我们可以用一个长度不超过 的二进制数来表示每一种技能是否被掌握。不妨记数组 req_skills 的长度为 ，数组 people 的长度为 。
我们先将 req_skills 中的每个技能映射到一个编号，即 表示技能 的编号。然后，我们遍历 people 中的每个人，将其掌握的技能用二进制数表示，即 表示编号为 的人掌握的技能。
接下来，我们定义以下三个数组，其中：
- 数组 表示掌握技能集合为 的最少人数，其中 的二进制表示中的每一位为 的位置，表示对应的技能被掌握。初始时 ，其余位置均为无穷大。
- 数组 表示掌握技能集合为 的最少人数时，最后一个人的编号。
- 数组 表示掌握技能集合为 的最少人数时，上一个技能集合状态。
我们在 的范围内枚举每个技能集合，对于每个技能集合 ：
我们枚举 people 中的每个人 ，如果 ，说明 可以通过 转移得到，此时，我们更新 为 ，并将 更新为 ，同时将 更新为 。即当前技能集合状态为 时，最后一个人的编号为 ，上一个技能集合状态为 。这里符号 表示按位或运算。
最后，我们从技能集合 开始，找到此时最后一个人的编号 ，将其加入答案中，然后将 更新为 ，不断地向前回溯，直到 ，即可得到最小的必要团队中的人员编号。
时间复杂度 ，空间复杂度 。其中 和 分别为 req_skills 和 people 的长度。
class Solution:
def smallestSufficientTeam(
self, req_skills: List[str], people: List[List[str]]
) -> List[int]:
d = {s: i for i, s in enumerate(req_skills)}
m, n = len(req_skills), len(people)
p = [0] * n
for i, ss in enumerate(people):
for s in ss:
p[i] |= 1 << d[s]
f = [inf] * (1 << m)
g = [0] * (1 << m)
h = [0] * (1 << m)
f[0] = 0
for i in range(1 << m):
if f[i] == inf:
continue
for j in range(n):
if f[i] + 1 < f[i | p[j]]:
f[i | p[j]] = f[i] + 1
g[i | p[j]] = j
h[i | p[j]] = i
i = (1 << m) - 1
ans = []
while i:
ans.append(g[i])
i = h[i]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(2^m * n) where m is the number of skills and n is the number of people, as each DP state can be updated for each person. Space complexity is O(2^m) for storing minimal teams per skill subset. |
| 空间 | O(2^m) |
面试官常问的追问
外企场景- question_mark
Expecting an efficient solution using bitmask DP rather than brute-force subsets.
- question_mark
Looking for handling of overlapping skills and minimizing team size simultaneously.
- question_mark
Interested in correct reconstruction of team indices from DP states.
常见陷阱
外企场景- error
Not mapping skills consistently to bits, leading to incorrect DP updates.
- error
Overwriting DP states without checking if the new team is smaller.
- error
Failing to backtrack properly to recover team indices.
进阶变体
外企场景- arrow_right_alt
Return the number of people in the smallest sufficient team instead of indices.
- arrow_right_alt
Find all possible smallest sufficient teams covering all skills.
- arrow_right_alt
Optimize for additional constraints like skill priorities or maximum team size.