LeetCode 1125. 最小的必要团队
题目描述
题意分析
从候选人员中选出尽量少的人，使团队掌握全部需求技能。返回这些人的原始编号，人数同样少时任意团队都可以。需求技能最多 16 种，人员最多 60 人，题目保证有解；人员可以没有技能，但其列出的技能都属于需求清单。
解法一：技能状态压缩动态规划
核心思路
[!blue]
人员子集最多有
2^60种，直接枚举不可行；需求技能只有 16 种，可以把已覆盖技能作为状态。给每种技能分配一位，一个人的技能就能编码成personMask，团队加入这个人后的覆盖范围是mask | personMask。全部技能已覆盖的状态为(1 << m) - 1。按人员顺序处理，令
count[mask]表示只使用已经处理的人，恰好覆盖技能集合mask所需的最少人数。相同覆盖状态只保留人数更少的团队：后续可选择的人员完全相同，技能覆盖也相同，多选的人不会让未来更有利。初始化count[0] = 0，其他状态设为n + 1，表示暂时不可达。处理第
i个人时，可以不选他，保留原状态；也可以从任一可达mask选他，得到next = mask | personMask，候选人数为count[mask] + 1。只有候选人数严格更少时才更新，人数相同则保留现有团队即可。没有技能的人不能改善任何状态，直接跳过。使用一维数组原地更新时，按
mask从大到小遍历。按位或只会增加位，因此next >= mask；若带来新技能，next > mask，这个较大状态本轮已经访问过，不会再被当作来源重复选择当前人。若没有带来新技能，next == mask，人数加一不可能改善自己。这样每次转移的来源仍对应此前的人员范围。题目还要返回人员编号，所以为每个技能状态保存一个人员位集合
team[mask]。人员至多 60 个，Java 的long和 Go 的uint64都足够，第i位表示是否选择此人。改进状态时同步记录team[next] = team[mask] | (1 << i)，其中移位必须使用 64 位的一。位集合按数值复制，不会因后续更新其他状态而改变已经保存的团队。每个人的选与不选都被枚举，并且同覆盖下较大人数的方案被安全淘汰。因此处理完所有人后，满技能状态就是人数最少的必要团队。依次检查该状态人员位集合中的置位，输出对应原始编号即可。
解题步骤
- 建立技能名到位下标的映射，创建人数表和 64 位人员集合表。
- 空技能状态的人数为零，其他状态初始化为不可达。
- 依次把每个人的技能转成
personMask，跳过没有技能的人。- 逆序遍历可达技能状态，尝试加入当前人；人数变少时同时更新人数和人员位集合。
- 取满技能状态的人员集合，输出每个置位对应的人员编号。
代码实现
class Solution {
public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
Map<String, Integer> skillIndex = new HashMap<>();
for (int i = 0; i < reqSkills.length; i++) {
skillIndex.put(reqSkills[i], i);
}
int n = people.size();
int states = 1 << reqSkills.length;
int inf = n + 1;
int[] count = new int[states];
Arrays.fill(count, inf);
count[0] = 0;
long[] team = new long[states];
for (int i = 0; i < n; i++) {
int personMask = 0;
for (String skill : people.get(i)) {
personMask |= 1 << skillIndex.get(skill);
}
if (personMask == 0) {
continue;
}
for (int mask = states - 1; mask >= 0; mask--) {
if (count[mask] == inf) {
continue;
}
int next = mask | personMask;
if (count[mask] + 1 < count[next]) {
count[next] = count[mask] + 1;
team[next] = team[mask] | (1L << i);
}
}
}
int[] answer = new int[count[states - 1]];
int index = 0;
for (int i = 0; i < n; i++) {
if ((team[states - 1] & (1L << i)) != 0) {
answer[index++] = i;
}
}
return answer;
}
}
func smallestSufficientTeam(reqSkills []string, people [][]string) []int {
skillIndex := make(map[string]int, len(reqSkills))
for i, skill := range reqSkills {
skillIndex[skill] = i
}
n := len(people)
states := 1 << len(reqSkills)
inf := n + 1
count := make([]int, states)
for mask := 1; mask < states; mask++ {
count[mask] = inf
}
team := make([]uint64, states)
for i, skills := range people {
personMask := 0
for _, skill := range skills {
personMask |= 1 << skillIndex[skill]
}
if personMask == 0 {
continue
}
for mask := states - 1; mask >= 0; mask-- {
if count[mask] == inf {
continue
}
next := mask | personMask
if count[mask]+1 < count[next] {
count[next] = count[mask] + 1
team[next] = team[mask] | (uint64(1) << i)
}
}
}
answer := make([]int, 0, count[states-1])
for i := 0; i < n; i++ {
if team[states-1]&(uint64(1)<<i) != 0 {
answer = append(answer, i)
}
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(C+n2^m)$，其中
m为需求技能数、n为人数、C为输入技能字符串总长度。建表与编码考虑字符串哈希成本，每个人最多扫描全部技能状态，最后扫描人员恢复答案。- 空间复杂度：$O(2^m+m)$，用于两个状态表与技能映射，不计返回数组。人员集合固定用一个 64 位整数表示。
关键点总结
[!green]
- 技能位集合表示覆盖状态，人员位集合保存具体答案，两者用途不同。
- 同样的覆盖范围只保留人数最少的团队，后续转移不会因此变差。
- 逆序更新利用
next >= mask，保证当前人不会在本轮重复参与转移。- 人数改善时同步更新人员集合，最终才能恢复与最优值一致的团队。
解法对比
枚举人员子集需要面对最多
2^60种选择；技能状态压缩把覆盖相同的方案合并，状态数最多只有2^16。这里的人员位集合只用于记录答案，并不枚举全部人员组合。
易错点总结
[!yellow]
- 技能合并应按位或，不能相加；重复掌握同一技能不会产生新的位。
- 不可达状态不能直接加一转移，否则会生成没有实际团队的候选。
- 只更新最少人数而不更新对应人员集合，会导致返回团队与最优值不一致。
- Java 的人员标记必须使用
1L << i，Go 使用uint64(1) << i，不能用 32 位整数保存最多 60 人。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 691. 贴纸拼词 | 困难 | 都把目标覆盖情况压缩成状态，每次加入一个候选扩展覆盖并最小化选择数量；贴纸还需处理重复字母和重复使用。 |