每日一题——最小的必要团队

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/smallest-sufficient-team 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = 1 << req_skills.length;


        // 1: 代表req_skill[0]的技能
        // 2: 代表req_skill[1]的技能
        // 4: 代表req_skill[2]的技能
        // 8: 代表req_skill[3]的技能

        // 1: 000001 -> dp[1]: req_skills[0] 需要几个人
        // 2: 000010 -> dp[2]: req_skills[1] 需要几个人
        // 3: 000011 -> dp[3]: req_skills[0] + req_skills[1] 需要几个人
        // 4: 000100 -> dp[4]: req_skills[2] 需要几个人
        // 5: 000101 -> dp[5]: req_skills[0] + req_skills[2] 需要几个人
        // 6: 000110 -> dp[6]: req_skills[0] + req_skills[1] 需要几个人


        // 最终要求的结果：dp[(1 << req_skills.length) - 1]
        List<Integer>[] dp = new ArrayList[n + 1];

        dp[0] = new ArrayList();


        // 状态:    000000 什么都不能做，是初始状态
        // 状态:    000001 代表只能做req_skills[0]的工作
        // 状态:    000010 代表只能做req_skills[1]的工作
        // 状态:    000011 代表能做req_skills[0] 和 req_skills[1]的工作

        // key: skill
        // value: 代表这个skill的num
        Map<String, Integer> skillToNumMap = transferSkillToNumMap(req_skills);


        for (int i=0; i<people.size(); i++) {

            // 我都能做点啥
            int iCanDoWhat = 0;

            List<String> skillList = people.get(i);
            for (String skill : skillList) {
                iCanDoWhat = iCanDoWhat | skillToNumMap.get(skill);
            }

            for (int j=0; j<dp.length; j++) {
                if (dp[j] == null) {
                    continue;
                }

                // 加上我之后都能做些啥
                int canDoWhatIfAddMe = j | iCanDoWhat;

                if (dp[canDoWhatIfAddMe] == null || dp[j].size() + 1 < dp[canDoWhatIfAddMe].size()) {
                    // 没有我不能做这些东西 或 需要的人数比之前计算的少，可以覆盖
                    List<Integer> list = new ArrayList<>(dp[j]);
                    list.add(i);
                    dp[canDoWhatIfAddMe] = list;
                }
            }

        }

        return dp[n - 1].stream().mapToInt(i -> i).toArray();
    }

    private Map<String, Integer> transferSkillToNumMap(String[] req_skills) {
        // key: skill
        // value: 代表这个skill的num
        Map<String, Integer> skillToNumMap = new HashMap<>();
        for (int i=0; i<req_skills.length; i++) {
            skillToNumMap.put(req_skills[i], 1 << i);
        }

        return skillToNumMap;
    }
    

更多内容欢迎关注公众号《写bug的西柚》