LeeCode 1125 并集最小组合-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeeCode 1125 并集最小组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，题目数据保证答案存在。
public int[] smallestSufficientTeam1(String[] req_skills, List<List<String>> people) {

        //1、映射
        //需要0,1,2,3,4,5 项技能
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < req_skills.length; i++) {
            map.put(req_skills[i], i);
        }

        int havePeople = people.size();
        int havaSkill = req_skills.length;
        List<Integer>[] listDp = new List[1 << havaSkill];//listDp[i]表示完成i项技能所需的最少人数的集合
        listDp[0] = new ArrayList<>();//listDp[0] ,空的集合，表示只需要0个人完成

        //2、查看people[i]在dp[]贡献
        for (int i = 0; i < havePeople; i++) {

            int iHaveSkill = 0;//i people拥有的技能
            for (String skill : people.get(i)
            ) {
                iHaveSkill |= (1 << map.get(skill));
            }
            System.out.println("i:"+i);
            System.out.println("people.get(i).size():"+people.get(i).size()+" cur_skill:"+iHaveSkill);

            // newHaveSkill = ihaveSkill | j
            // dp[newHaveSkill] = min(dp[j] + 1,dp[newHaveSkill])

            for (int j = 0; j < listDp.length; j++) {
                if (listDp[j] == null)
                    continue;
                int newHaveSkill = j | iHaveSkill;
                if (listDp[newHaveSkill] == null || listDp[j].size() + 1 < listDp[newHaveSkill].size()){
                    listDp[newHaveSkill] = new ArrayList<>(listDp[j]);
                    listDp[newHaveSkill].add(i);
                }
            }
        }

//        System.out.println("listDp[listDp.length-1]:"+listDp.length);
        int len = listDp[(1 << havaSkill)-1].size();
        int[] res = new int[len];
        for (int i = 0; i < len;i++){
            res[i] = listDp[(1 << havaSkill)-1].get(i);
        }
        return res;

    }
思路解析：

1、集合A中共有0，1，2，3，4，5...元素

2、子集1拥有0，1，2 ；子集2拥有3，5；子集3拥有3, 4, 5

3、问题转化，最少合并子集个数，组合成集合A

4、子集组合【0/1】【0/1】【0/1】，选择当前集合或者不选择当前集合

最大不过是1 1 1，长度

问题求解：dp[8]中元素最少的个数

已知dp[pre] ，现有集合中拥有x个元素，dp[x|pre] 添加当前元素后的集合

dp[x|pre] = dp[pre] +1 或者不变文章来源地址https://www.toymoban.com/news/detail-411829.html