最少猎头拿到全部简历问题

最少猎头拿到全部简历问题

题目

已知猎头跟简历的对应关系，猎头手中的简历可能重叠。找到能获取全部简历的最少猎头

eg: A 1 2 3 4 B 2 3 5 C 4 5 6 D 5 6 7 8 E 1 4 6 result: [A, D]

面试官：能做出来吗？ 我：目前能想到的就是贪心算法（一直要简历最多的猎头，但是有可能拿到的不是最优解），可以用回溯解决吗？ 面试官：你可以试一下

public class Solution { public static void main(String[] args) { Solution solution = new Solution(); // 标记猎头及其拥有的简历 HashMap> listMap1 = new HashMap<>(); listMap1.put("A", Arrays.asList(1, 2, 3, 4)); listMap1.put("B", Arrays.asList(2, 3, 5)); listMap1.put("C", Arrays.asList(4, 5, 6)); listMap1.put("D", Arrays.asList(5, 6, 7, 8)); listMap1.put("E", Arrays.asList(1, 4, 6)); // [A, D] System.out.println(solution.query(listMap1)); HashMap> listMap = new HashMap<>(); // 测试贪心算法错误的情况 listMap.put("A", Arrays.asList(1, 3, 4, 5)); listMap.put("B", Arrays.asList(1, 3, 6)); listMap.put("C", Arrays.asList(2, 4, 5)); listMap.put("D", Arrays.asList(1, 3, 6)); // [C, D] System.out.println(solution.query(listMap)); } public List query(Map> map){ Set set = new HashSet<>(); List nameList = new ArrayList<>(); List finalList = new ArrayList<>(); Map> nameNumMap = new LinkedHashMap<>(); int num = 0; for (Map.Entry> m : map.entrySet()) { set.addAll(m.getValue()); nameList.add(m.getKey()); nameNumMap.put(num, m.getValue()); num++; } int[] visitor = new int[nameList.size()]; int minTotalNum = nameList.size(); dfs(0, set.size(), nameList.size(), nameList, nameNumMap, visitor, minTotalNum, finalList); return finalList; } /** * @param index 决定index个猎头是否选择 * @param visitorNum 面试者总数 * @param headNum 猎头总数 * @param nameList 猎头名字 * @param nameNumMap 数字->猎头拥有的简历 * @param visit 标志是否取猎头的简历 * @param minTotalNum 暂存获取全部简历的最少猎头数 * @param finalList 最终选择的猎头名字 */ public void dfs(int index, int visitorNum, int headNum, List nameList, Map> nameNumMap, int[] visit, int minTotalNum, List finalList) { if (index > headNum) { return; } if (index == headNum) { // 选了几个猎头 int total = 0; // 存放猎头的名字 List tempNameList = new ArrayList<>(); // 拿到的简历 Set set = new HashSet<>(); for (int i = 0; i < headNum; i++) { if (visit[i] == 1) { total++; tempNameList.add(nameList.get(i)); // 标记面试官中的简历 List list = nameNumMap.get(i); set.addAll(list); } } // 能拿到所有的简历 if (set.size() == visitorNum) { if (total <= minTotalNum) { finalList.clear(); finalList.addAll(tempNameList); } } } else { for (int i = 0; i < headNum; i++) { // 取第i个猎头 visit[i] = 1; dfs(index + 1, visitorNum, headNum, nameList, nameNumMap, visit, minTotalNum, finalList); visit[i] = 0; } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。