列表

详情

1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

 

示例 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]

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) { } };

golang 解法, 执行用时: 16 ms, 内存消耗: 5.5 MB, 提交时间: 2023-04-08 22:06:41 

func smallestSufficientTeam(req_skills []string, people [][]string) []int {
    n, m := len(req_skills), len(people)
    skill_index := make(map[string]int)
    for i, skill := range req_skills {
        skill_index[skill] = i
    }
    dp := make([]int, 1 << n)
    for i := range dp {
        dp[i] = m
    }
    dp[0] = 0
    prev_skill := make([]int, 1 << n)
    prev_people := make([]int, 1 << n)
    for i := 0; i < m; i++ {
        cur_skill := 0
        for _, s := range people[i] {
            cur_skill |= 1 << skill_index[s]
        }
        for prev := 0; prev < (1 << n); prev++ {
            comb := prev | cur_skill
            if dp[comb] > dp[prev]+1 {
                dp[comb] = dp[prev] + 1
                prev_skill[comb] = prev
                prev_people[comb] = i
            }
        }
    }
    res := []int{}
    i := (1 << n) - 1
    for i > 0 {
        res = append(res, prev_people[i])
        i = prev_skill[i]
    }
    return res
}

python3 解法, 执行用时: 768 ms, 内存消耗: 17.2 MB, 提交时间: 2023-04-08 22:06:19 

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        skill_index = {v: i for i, v in enumerate(req_skills)}
        dp = [m] * (1 << n)
        dp[0] = 0
        prev_skill = [0] * (1 << n)
        prev_people = [0] * (1 << n)
        for i, p in enumerate(people):
            cur_skill = 0
            for s in p:
                cur_skill |= 1 << skill_index[s]
            for prev in range(1 << n):
                comb = prev | cur_skill
                if dp[comb] > dp[prev] + 1:
                    dp[comb] = dp[prev] + 1
                    prev_skill[comb] = prev
                    prev_people[comb] = i
        res = []
        i = (1 << n) - 1
        while i > 0:
            res.append(prev_people[i])
            i = prev_skill[i]
        return res

golang 解法, 执行用时: 24 ms, 内存消耗: 36.3 MB, 提交时间: 2023-04-08 22:05:11 

func smallestSufficientTeam(reqSkills []string, people [][]string) (ans []int) {
    m := len(reqSkills)
    sid := make(map[string]int, m)
    for i, s := range reqSkills {
        sid[s] = i // 字符串映射到下标
    }

    n := len(people)
    mask := make([]int, n)
    for i, skills := range people {
        for _, s := range skills { // 把 skills 压缩成一个二进制数 mask[i]
            mask[i] |= 1 << sid[s]
        }
    }

    u, all := 1<<m, 1<<n-1
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, u)
        for j := range memo[i] {
            memo[i][j] = -1 // -1 表示还没有计算过
        }
    }
    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if j == 0 { // 背包已装满
            return 0
        }
        if i < 0 { // 没法装满背包，返回全集，这样下面比较集合大小会取更小的
            return all
        }
        p := &memo[i][j]
        if *p != -1 {
            return *p
        }
        r1 := dfs(i-1, j) // 不选 mask[i]
        r2 := dfs(i-1, j&^mask[i]) | 1<<i // 选 mask[i]
        if bits.OnesCount(uint(r1)) < bits.OnesCount(uint(r2)) {
            *p = r1
        } else {
            *p = r2
        }
        return *p
    }
    res := dfs(n-1, u-1)

    for i := 0; i < n; i++ {
        if res>>i&1 > 0 {
            ans = append(ans, i) // 所有在 res 中的下标
        }
    }
    return
}

java 解法, 执行用时: 33 ms, 内存消耗: 103.9 MB, 提交时间: 2023-04-08 22:04:57 

class Solution {
    private long all;
    private int[] mask;
    private long[][] memo;

    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        var sid = new HashMap<String, Integer>();
        int m = reqSkills.length;
        for (int i = 0; i < m; ++i)
            sid.put(reqSkills[i], i); // 字符串映射到下标

        int n = people.size();
        mask = new int[n];
        for (int i = 0; i < n; ++i)
            for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask[i]
                mask[i] |= 1 << sid.get(s);

        int u = 1 << m;
        memo = new long[n][u];
        for (int i = 0; i < n; i++)
            Arrays.fill(memo[i], -1); // -1 表示还没有计算过
        all = (1L << n) - 1;
        long res = dfs(n - 1, u - 1);

        var ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; ++i)
            if (((res >> i) & 1) > 0)
                ans[j++] = i; // 所有在 res 中的下标
        return ans;
    }

    private long dfs(int i, int j) {
        if (j == 0) return 0; // 背包已装满
        if (i < 0) return all; // 没法装满背包，返回全集，这样下面比较集合大小会取更小的
        if (memo[i][j] != -1) return memo[i][j];
        long res = dfs(i - 1, j); // 不选 mask[i]
        long res2 = dfs(i - 1, j & ~mask[i]) | (1L << i); // 选 mask[i]
        return memo[i][j] = Long.bitCount(res) < Long.bitCount(res2) ? res : res2;
    }
}

python3 解法, 执行用时: 528 ms, 内存消耗: 118.4 MB, 提交时间: 2023-04-08 22:04:44 

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        sid = {s: i for i, s in enumerate(req_skills)}  # 字符串映射到下标
        n = len(people)
        mask = [0] * n
        for i, skills in enumerate(people):
            for s in skills:  # 把 skills 压缩成一个二进制数 mask[i]
                mask[i] |= 1 << sid[s]

        # dfs(i,j) 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合
        @cache
        def dfs(i: int, j: int) -> int:
            if j == 0: return 0  # 背包已装满
            if i < 0: return (1 << n) - 1  # 没法装满背包，返回全集，这样下面比较集合大小会取更小的
            res = dfs(i - 1, j)  # 不选 mask[i]
            res2 = dfs(i - 1, j & ~mask[i]) | (1 << i)  # 选 mask[i]
            return res if res.bit_count() < res2.bit_count() else res2

        res = dfs(n - 1, (1 << len(req_skills)) - 1)
        return [i for i in range(n) if (res >> i) & 1]  # 所有在 res 中的下标

上一题

© 2024 leetcode.cn