LeetCode每日一题（2023/4/8）

1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 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 中的技能
题目数据保证「必要团队」一定存在

解答：这段代码首先将每个人的技能表示为一个整数，并将每个整数值存储在peopleSkills数组中。然后，它使用动态规划的方法计算最小团队大小，将结果存储在dp数组中。最后，它从动态规划数组中提取结果，并返回一个包含所选团队成员索引的数组。

class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        // 将技能映射到整数索引
        Map<String, Integer> skillToIndex = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            skillToIndex.put(req_skills[i], i);
        }
        // 将每个人的技能表示为一个整数值
        int[] peopleSkills = new int[people.size()];
        for (int i = 0; i < people.size(); ++i) {
            for (String skill : people.get(i)) {
                int index = skillToIndex.getOrDefault(skill, -1);
                if (index != -1) {
                    peopleSkills[i] |= 1 << index;
                }
            }
        }
        // 使用动态规划计算最小团队大小
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        // 记录状态转移的前一个状态
        Map<Integer, Integer> prevState = new HashMap<>();
        // 记录将某个人添加到状态的映射
        Map<Integer, Integer> addToState = new HashMap<>();

        for (int i = 0; i < people.size(); ++i) {
            int k = peopleSkills[i];
            if (k == 0) {
                continue;
            }
            for (int j = (1 << n) - 1; j >= 0; --j) {
                if (dp[j] == -1) {
                    continue;
                }
                int newStatus = j | k;
                if (dp[newStatus] == -1 || dp[newStatus] > dp[j] + 1) {
                    dp[newStatus] = dp[j] + 1;
                    prevState.put(newStatus, j);
                    addToState.put(newStatus, i);
                }
            }
        }

        // 从动态规划数组中提取结果
        int[] ans = new int[dp[(1 << n) - 1]];
        int state = (1 << n) - 1;
        for (int i = ans.length - 1; i >= 0; --i) {
            ans[i] = addToState.get(state);
            state = prevState.get(state);
        }

        return ans;
    }
}