1125：最小的必要团队（2250 分）

Ian

2019-07-14 约 726 字预计阅读 2 分钟次阅读

力扣第 145 场周赛第 4 题

题目

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

相似问题：

分析

#1

典型的状压 dp
令 f(i,st) 代表 peope[:i] 掌握技能集合 st 的最小团队集合，即可递推

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        d = {x:i for i,x in enumerate(req_skills)}
        m,n = len(people),len(d)
        f = [(1<<m)-1]*(1<<n) 
        f[0] = 0
        for i,A in enumerate(people):
            st0 = sum(1<<d[a] for a in A)
            for st in range((1<<n)-1,-1,-1):
                if f[st].bit_count()==m:
                    continue
                st2 = st|st0
                if 1+f[st].bit_count()<f[st2].bit_count():
                    f[st2] = f[st]|1<<i
        return [i for i in range(m) if f[-1]>>i&1]

455 ms

#2

还可以令 f、g 分别代表最小团队的大小和集合，节省 bit_count() 的时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        d = {x:i for i,x in enumerate(req_skills)}
        m,n = len(people),len(d)
        f = [m]*(1<<n)
        g = [(1<<m)-1]*(1<<n) 
        f[0] = g[0] = 0
        for i,A in enumerate(people):
            st0 = sum(1<<d[a] for a in A)
            for st in range((1<<n)-1,-1,-1):
                if f[st]==m:
                    continue
                st2 = st|st0
                if 1+f[st]<f[st2]:
                    f[st2] = 1+f[st]
                    g[st2] = g[st]|1<<i
        return [i for i in range(m) if g[-1]>>i&1]

236 ms

目录

1125：最小的必要团队（2250 分）

题目

分析

#1

#2

解答