Hard

题目描述

在一个项目中，你有一个所需技能列表 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 <= 16
  • 1 <= req_skills[i].length <= 16
  • req_skills[i] 由小写英文字母组成
  • req_skills 的所有字符串都是唯一的
  • 1 <= people.length <= 60
  • 0 <= people[i].length <= 16
  • 1 <= people[i][j].length <= 16
  • people[i][j] 由小写英文字母组成
  • people[i] 的所有字符串都是唯一的
  • people[i] 中的每个技能都在 req_skills 中
  • 题目保证存在足够的团队

解题思路

这是一道典型的状态压缩动态规划问题。由于技能数量最多16个，我们可以用二进制数表示技能集合，每一位代表一个技能。

核心思路：

  1. 状态表示：用二进制数 mask 表示已掌握的技能集合，第 i 位为1表示掌握第 i 个技能
  2. 状态转移：对于每个人，尝试将其加入团队，更新能达到的技能组合
  3. 最优化目标：找到覆盖所有技能的最小团队

算法步骤：

  1. 将技能名称映射到索引，方便位运算
  2. 将每个人的技能转换为二进制表示
  3. 使用动态规划：dp[mask] 表示达到技能集合 mask 所需的最小团队
  4. 遍历每个人，对于每个已有状态，尝试加入当前人员
  5. 目标状态是 (1 << n) - 1，即所有技能都被覆盖

优化细节：

  • 使用队列进行BFS式的状态转移，确保找到最小团队
  • 记录路径信息，便于重构最终答案
  • 剪枝：如果当前团队大小已经不优于已知解，跳过

代码实现

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = req_skills.size();
        unordered_map<string, int> skillIndex;
        for (int i = 0; i < n; i++) {
            skillIndex[req_skills[i]] = i;
        }
        
        vector<int> peopleMask(people.size());
        for (int i = 0; i < people.size(); i++) {
            for (const string& skill : people[i]) {
                peopleMask[i] |= 1 << skillIndex[skill];
            }
        }
        
        vector<vector<int>> dp(1 << n, vector<int>(61, -1));
        dp[0][0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int size = 0; size <= 60; size++) {
                if (dp[mask][size] == -1) continue;
                
                for (int i = 0; i < people.size(); i++) {
                    int newMask = mask | peopleMask[i];
                    if (dp[newMask][size + 1] == -1) {
                        dp[newMask][size + 1] = i;
                    }
                }
            }
        }
        
        int targetMask = (1 << n) - 1;
        int minSize = 61;
        for (int size = 1; size <= 60; size++) {
            if (dp[targetMask][size] != -1) {
                minSize = size;
                break;
            }
        }
        
        vector<int> result;
        int currentMask = targetMask;
        int currentSize = minSize;
        
        while (currentMask > 0) {
            int person = dp[currentMask][currentSize];
            result.push_back(person);
            currentMask ^= peopleMask[person];
            currentSize--;
        }
        
        return result;
    }
};

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        skill_index = {skill: i for i, skill in enumerate(req_skills)}
        
        people_mask = []
        for person_skills in people:
            mask = 0
            for skill in person_skills:
                mask |= 1 << skill_index[skill]
            people_mask.append(mask)
        
        dp = {}
        dp[0] = []
        
        for i, mask in enumerate(people_mask):
            new_dp = dp.copy()
            for covered, team in dp.items():
                new_covered = covered | mask
                if new_covered not in new_dp or len(new_dp[new_covered]) > len(team) + 1:
                    new_dp[new_covered] = team + [i]
            dp = new_dp
        
        return dp[(1 << n) - 1]

public class Solution {
    public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
        int n = req_skills.Length;
        var skillIndex = new Dictionary<string, int>();
        for (int i = 0; i < n; i++) {
            skillIndex[req_skills[i]] = i;
        }
        
        var peopleMask = new int[people.Count];
        for (int i = 0; i < people.Count; i++) {
            foreach (string skill in people[i]) {
                peopleMask[i] |= 1 << skillIndex[skill];
            }
        }
        
        var dp = new Dictionary<int, List<int>>();
        dp[0] = new List<int>();
        
        for (int i = 0; i < people.Count; i++) {
            var newDp = new Dictionary<int, List<int>>(dp);
            foreach (var kvp in dp) {
                int covered = kvp.Key;
                var team = kvp.Value;
                int newCovered = covered | peopleMask[i];
                
                if (!newDp.ContainsKey(newCovered) || newDp[newCovered].Count > team.Count + 1) {
                    newDp[newCovered] = new List<int>(team) { i };
                }
            }
            dp = newDp;
        }
        
        return dp[(1 << n) - 1].ToArray();
    }
}

var smallestSufficientTeam = function(req_skills, people) {
    const n = req_skills.length;
    const skillIndex = new Map();
    for (let i = 0; i < n; i++) {
        skillIndex.set(req_skills[i], i);
    }
    
    const peopleMask = people.map(personSkills => {
        let mask = 0;
        for (const skill of personSkills) {
            mask |= 1 << skillIndex.get(skill);
        }
        return mask;
    });
    
    const dp = new Map();
    dp.set(0, []);
    
    for (let i = 0; i < people.length; i++) {
        const newDp = new Map(dp);
        for (const [covered, team] of dp) {
            const newCovered = covered | peopleMask[i];
            if (!newDp.has(newCovered) || newDp.get(newCovered).length > team.length + 1) {
                newDp.set(newCovered, [...team, i]);
            }
        }
        dp.clear();
        for (const [key, value] of newDp) {
            dp.set(key, value);
        }
    }
    
    return dp.get((1 << n) - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(people × 2^skills)
空间复杂度O(2^skills × people)

其中 skills 是技能数量（最多16），people 是人员数量（最多60）。由于使用状态压缩，每个状态对应一个技能组合，最多有 2^16 个状态。

相关题目