Leetcode.1125 最小的必要团队

题目链接

Leetcode.1125 最小的必要团队 Rating ： 2251

题目描述

作为项目经理，你规划了一份需求的技能清单 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<=reqskills.length<=161 <= req_skills.length <= 161<=reqs​kills.length<=16
• 1<=reqskills[i].length<=161 <= req_skills[i].length <= 161<=reqs​kills[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中的技能
• 题目数据保证「必要团队」一定存在

解法：状压dp

首先我们先用一个哈希表 $sid$ 将 req_skills中的每一个技能 映射成 对应的下标。比如 req_skills = [ "Java" , "C++" , "JS"]，即 "Java" -> 0 , "C++" -> 1 , "JS" -> 2。

对于 people，我们可以把 people[i]看作是一个集合 $mask$。如果 mask=1101(2)mask = 1101_{(2)}mask=1101(2)​则说明，该集合能够掌握技能 req_skills[0] , req_skills[2] , req_skills[3]。

我们的目的就是 用最少的这样的集合 能够让其掌握 req_skills所有的技能。

接着，我们再使用 01背包 的方式求解。对于每一个集合 people[i]，我们只需要讨论 选 还是 不选。

我们定义 $f(i)$ 为 能够表示 状态 $i$ 的最小的集合。按照定义 $f((1<<m)-1)$就是我们的答案，因为我们选择的集合要使 req_skills的每一个技能都被选中，即 m 位二进制数都表示为 1 ，也就是 $(1<<m)-1$。

用于我们最终的答案 $f((1<<m)-1)$ 所表示的也是一个集合，代表选择了 哪些 people[i]。所以最后我们也要将具体选择的是 哪些 $i$ 存入到答案 ans中，最后返回 ans即可。

时间复杂度： O(2m∗n+m)O(2 ^ m * n + m)O(2m∗n+m)

C++代码：

using LL = long long;
class Solution {
public:vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {int m = req_skills.size();unordered_map<string,int> sid;for(int i = 0;i < m;i++){sid[req_skills[i]] = i;}int n = people.size();int u = 1 << m;//初始时 每一个状态都表示全集vector<LL> f(u , (1LL << n) - 1);f[0] = 0; for(int i = 0;i < n;i++){int mask = 0;for(auto &s:people[i]){mask |= (1 << sid[s]);}for(int j = u - 1;j >= 0;j--){//不选 peopele[i]auto a = f[j];//选 people[i]auto b = f[j & (~mask)] | (1LL << i);//选择更小的集合f[j] = __builtin_popcountll(a) < __builtin_popcountll(b) ? a : b;}}auto res = f[u - 1];vector<int> ans;for(int i = 0;i < n;i++){if((res >> i) & 1) ans.push_back(i);}return ans;}
};