LeetCode 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]

题目解析

1. 集合覆盖问题，求最右解需使用暴力解法。
2. 将技能和人员进行状态压缩
3. 使用顺退过程尝试对每一个团队状态添加任务，添加后得到新的团队状态，若人数比之前少，则更新新状态团队任务。
   dp[newskill] = min(dp[newskill], dp[skill] | k), 其中k为添加人员的skill

C++代码

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int skLen = (1 << req_skills.size()) - 1;
        int peLen = people.size();
        vector<int> vecA(skLen + 1, 0);
        vector<int> vecB(skLen + 1, 0);
        vector<int> vecLen(skLen + 1, peLen);
        vector<int> ans;
        vecLen[0] = 0;
        map<string, int> skMap;
        for(int i = 0 ; i < req_skills.size(); i++) {
            skMap[req_skills[i]] = i;
        }

        for(int i = 0; i < people.size();i++) {
            int skill = 0;
            for(int j = 0; j < people[i].size(); j++) {
                skill |= (1 << skMap[people[i][j]]);
            }
        
            for(int j = 0; j < skLen; j++) {
                int nskill = j | skill;                
                if(nskill != j && vecLen[nskill] > vecLen[j] + 1) {
                    vecLen[nskill]=vecLen[j] + 1;
                    if(i < 30) {                        
                        vecA[nskill] = vecA[j] | (1 << i);  
                        vecB[nskill] = vecB[j];
                    } else {
                        vecA[nskill] = vecA[j];
                        vecB[nskill] = vecB[j] | (1 << (i-30));                        
                    }
                    
                }
            }
        }
        int i = 0;
        
        while(vecA[skLen]) {
            if((vecA[skLen] & 1) != 0) {
                ans.push_back(i);
            }
            vecA[skLen] >>= 1;
            i++;
        }
        
        i = 0;
        
        while(vecB[skLen]) {
            if((vecB[skLen] & 1) != 0) {
                ans.push_back(i+30);
            }
            vecB[skLen] >>= 1;
            i++;
        }
        
        return ans;
    }
};