algorithm-class/算法周更班/class_2023_05_2_week/Code03_SmallestSufficientTeam.java

package class_2023_05_2_week;

import java.util.Arrays;
import java.util.List;

// 作为项目经理，你规划了一份需求的技能清单 req_skills，
// 并打算从备选人员名单 people 中选出些人组成一个「必要团队」
//（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
// 所谓「必要团队」，就是在这个团队中，
// 对于所需求的技能列表 req_skills 中列出的每项技能，
// 团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
// 例如，团队 team = [0, 1, 3] 表示掌握技能分别为
// people[0]，people[1]，和 people[3] 的备选人员。
// 请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。
// 你可以按 任意顺序 返回答案，题目数据保证答案存在。
// 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/
public class Code03_SmallestSufficientTeam {

	// 需要的技能有 : "ABC" 、 "FG" 、 "ET"
	// 人 ： "ABC" "ET" "BB"
	// "ABC" 、 "FG" 、 "ET" -> "ABC" "ET" "FG" 
	//                           0     1    2
	// x  : "ABC" "ET" "BB" :      2   1    0
	//                             0   1    1
	public static int[] smallestSufficientTeam(String[] skills, List<List<String>> people) {
		Arrays.sort(skills);
		int n = skills.length;
		int m = people.size();
		int[] statuses = new int[m];
		for (int i = 0; i < m; i++) {
			int skillStatus = 0; // 00000000000000
			List<String> skill = people.get(i);
			skill.sort((a, b) -> a.compareTo(b));
			int p1 = 0;
			int p2 = 0;
			while (p1 < n && p2 < skill.size()) {
				int compare = skills[p1].compareTo(skill.get(p2));
				if (compare < 0) {
					p1++;
				} else if (compare > 0) {
					p2++;
				} else {
					skillStatus |= 1 << p1;
					p1++;
					p2++;
				}
			}
			statuses[i] = skillStatus;
		}
		// 上面的过程，其实是把技能变成状态信息
		// 比如:
		// skills = { f,a,e,c}
		// 排个序为 : a c e f
		// 认为a是0技能
		// 认为c是1技能
		// 认为e是2技能
		// 认为f是3技能
		// 然后就可以把每个人的技能变成状态信息了
		// 比如，A会的技能 : e f t x c
		//                    feca
		// 认为A会的技能状态为 : 1110
		// 解释一下 :
		// 第0位是0，说明A不会a技能
		// 第1位是1，说明A会c技能
		// 第2位是1，说明A会e技能
		// 第3位是1，说明A会f技能
		// 至于t、x技能，忽略！因为没用
		// 上面的过程，就是把技能编号
		// 然后把每个人的技能变成位信息
		// 比如skills一共8个技能
		// 那么就是为了这个状态 : 00..0011111111
		// 也就是什么时候凑齐8个1，什么时候就可以结束了！
		int[][] dp = new int[m][1 << n];
		for (int i = 0; i < m; i++) {
			Arrays.fill(dp[i], -1);
		}
		// process函数去跑动态规划
		// 目的是算出至少几人
		// 以及填好动态规划表
		int size = process(statuses, n, 0, 0, dp);
		int[] ans = new int[size];
		int ansi = 0;
		int i = 0;
		int status = 0;
		// 大厂刷题班，章节11
		// 看一下，是根据动态规划表生成答案的路径
		// 这就是为什么需要动态规划表，因为答案的路径可以用动态规划表生成
		// 一定要看一下这个课
		while (status != (1 << n) - 1) {
			//                    3人                 3人
			if (i + 1 == m || dp[i][status] != dp[i + 1][status]) {
				ans[ansi++] = i;
				status |= statuses[i];
			}
			i++;
		}
		return ans;
	}

	// 第i个人的技能列表，是位信息！就是people[i]！people数组是固定参数
	// 一定要凑齐n个技能，n是固定参数
	// 当前来到第i个人了，可以要这个人，也可以不要这个人，i是可变信息！
	// 之前的技能，哪个技能凑到了，哪个技能还没凑到，就是status！你的目的是把它凑齐！也就是凑齐n个1！stauts是可变参数
	// 返回值的含义 :
	// 当前在people[i....]范围上选择人，之前凑齐的技能状态是status，请问所有技能都凑齐，还需要至少几个人
	// dp就是动态规划表，记录返回值的！
	public static int process(int[] people, int n, int i, int status, int[][] dp) {
		// n = 8
		//    0000...0000 1111 1111 
		if (status == (1 << n) - 1) {
			// 技能已经凑齐了
			// 还需要0个人
			return 0;
		}
		// 还没凑齐！
		if (i == people.length) {
			// 技能还没凑齐
			// 但是人已经没了
			// 怎么都凑不齐了
			return Integer.MAX_VALUE;
		}
		if (dp[i][status] != -1) {
			// 缓存命中，直接返回
			return dp[i][status];
		}
		// 不要第i个人，后续要几个人能凑齐
		int p1 = process(people, n, i + 1, status, dp);
		// 要第i个人，后续要几个人能凑齐
		int p2 = Integer.MAX_VALUE;
		int next2 = process(people, n, i + 1, status | people[i], dp);
		if (next2 != Integer.MAX_VALUE) {
			p2 = 1 + next2;
		}
		// 选择人数最少的方案
		int ans = Math.min(p1, p2);
		dp[i][status] = ans;
		return ans;
	}

}