2023-09-10：用 go 语言编写。作为项目经理，你规划了一份需求的技能清单 req_skills，
并打算从备选人员名单 people 中选出些人组成一个「必要团队」
（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，
对于所需求的技能列表 req_skills 中列出的每项技能，
团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
例如，团队 team = [0, 1, 3] 表示掌握技能分别为
people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。
你可以按 任意顺序 返回答案，题目数据保证答案存在。
输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]。
输出：[0,2]。
来自左程云。
答案 2023-09-10：
大体步骤如下：
1.首先，我们对 reqSkills 进行排序，获得排序后的技能列表。这是为了后续方便进行比较。例如，将 ["java", "nodejs", "reactjs"] 排序为 ["java", "nodejs", "reactjs"]。
2.初始化变量 n 为 reqSkills 的长度，变量 m 为 people 的长度，并创建一个长度为 m 的整数数组 statuses 用于记录每个人的技能状态。
3.对于每个人，我们通过比较技能列表和排序后的 reqSkills 列表，来确定他们掌握的技能状态。首先，将该人的技能列表排序。然后使用双指针法，一个指针指向排序后的 reqSkills 列表，另一个指针指向该人的技能列表。比较两个指针指向的技能，如果相等，则表示该人掌握了该技能，将对应的状态位置为 1，并将两个指针都向后移动一位；如果 reqSkills[p1] 小于 skill[p2]，则将指向 reqSkills 的指针向后移动一位；否则将指向技能列表的指针向后移动一位。重复这个过程直到其中一个指针超出范围。
4.将每个人的技能状态记录在 statuses 数组中。
5.创建一个二维数组 dp，其中 dp[i][j] 表示从第 i 个人开始，技能状态为 j 时，所需的最小团队人数。初始化 dp 数组的所有元素为 -1。
6.调用递归函数 process，该函数的参数包括：people 数组，技能列表的长度 n，当前处理的人员下标 i，当前的技能状态 status，以及 dp 数组。
7.在递归函数 process 中，首先判断当前技能状态是否已经满足所有需求，即 status 是否等于 (1<<n)-1。如果满足，则返回 0 表示不需要再增加人员。
8.接下来，判断是否已经遍历了所有人员，即 i 是否等于 people 数组的长度。如果是，说明无法满足所有需求，并返回一个较大的值，这里使用 1<<31-1 来表示无穷大。
9.然后，判断 dp 数组中是否已经记录了当前人员和技能状态的最小团队人数，如果是，直接返回该值。
10.在递归函数中，我们有两个递归调用，第一个是继续尝试从下一个人员开始不增加人员的情况，即调用 process(people, n, i+1, status, dp)，将返回的值保存在变量 p1 中。
11.第二个递归调用是尝试从下一个人员开始增加当前人员的情况，即调用 process(people, n, i+1, status|people[i], dp)，将返回的值保存在变量 p2 中。注意，这里的参数 status|people[i] 表示将当前人员的技能状态添加到当前技能状态中。
12.如果 p2 不等于 1<<31-1，说明可以满足当前需求，将 p2+1 指代的团队人数保存在变量 ans 中，否则将 ans 设置为 p1。
13.将 ans 保存在 dp 数组中以便下次使用，并返回 ans。
14.在主函数中，根据返回的最小团队人数 size，创建一个大小为 size 的整数数组 ans 和一个指示 ans 数组下标的变量 ansi。
15.初始化变量 i 为 0，status 为 0，用于记录当前处理的人员下标和技能状态。
16.如果 status 不等于 (1<<n)-1，即还没有满足所有需求，执行循环。在循环中，判断两个条件：如果 i+1 等于 m，说明已经遍历到了最后一个人员；如果 dp[i][status] 不等于 dp[i+1][status]，表示从当前人员开始增加人员可以满足当前需求。
17.如果满足上述两个条件之一，将 i 添加到 ans 数组中，并将 ansi 自增 1。然后将当前人员的技能状态添加到当前技能状态中。
18.无论是否满足条件，将 i 自增 1。
19.执行完循环后，返回 ans 数组作为结果。
总的时间复杂度为 O(m * (2^n))，额外空间复杂度为 O(m * (2^n))。
go 完整代码如下：
package main
import ( "fmt" "sort")
func smallestSufficientTeam(reqSkills []string, people [][]string) []int { sort.Strings(reqSkills) n := len(reqSkills) m := len(people) statuses := make([]int, m) for i := 0; i < m; i++ { skillStatus := 0 skill := people[i] sort.Strings(skill) p1, p2 := 0, 0 for p1 < n && p2 < len(skill) { compare := reqSkills[p1] == skill[p2] if compare { skillStatus |= 1 << p1 p1++ p2++ } else if reqSkills[p1] < skill[p2] { p1++ } else { p2++ } } statuses[i] = skillStatus }
dp := make([][]int, m) for i := 0; i < m; i++ { dp[i] = make([]int, 1<<n) for j := 0; j < 1<<n; j++ { dp[i][j] = -1 } }
size := process(statuses, n, 0, 0, dp) ans := make([]int, size) ansi := 0 i := 0 status := 0 for status != (1<<n)-1 { if i+1 == m || dp[i][status] != dp[i+1][status] { ans[ansi] = i ansi++ status |= statuses[i] } i++ } return ans}
func process(people []int, n, i, status int, dp [][]int) int { if status == (1<<n)-1 { return 0 } if i == len(people) { return 1<<31 - 1 } if dp[i][status] != -1 { return dp[i][status] } p1 := process(people, n, i+1, status, dp) p2 := 1<<31 - 1 next2 := process(people, n, i+1, status|people[i], dp) if next2 != 1<<31-1 { p2 = 1 + next2 } ans := min(p1, p2) dp[i][status] = ans return ans}
func min(a, b int) int { if a < b { return a } return b}
func main() { reqSkills := []string{"java", "nodejs", "reactjs"} people := [][]string{{"java"}, {"nodejs"}, {"nodejs", "reactjs"}}
result := smallestSufficientTeam(reqSkills, people) fmt.Println(result)}
复制代码
rust 完整代码如下：
fn smallest_sufficient_team(req_skills: Vec<String>, people: Vec<Vec<String>>) -> Vec<i32> { let n = req_skills.len(); let m = people.len(); let mut statuses = vec![0; m]; for (i, skill) in people.iter().enumerate() { let mut skill_status = 0; let mut sorted_skill = skill.clone(); sorted_skill.sort(); let mut p1 = 0; let mut p2 = 0; while p1 < n && p2 < sorted_skill.len() { match req_skills[p1].cmp(&sorted_skill[p2]) { std::cmp::Ordering::Less => p1 += 1, std::cmp::Ordering::Greater => p2 += 1, std::cmp::Ordering::Equal => { skill_status |= 1 << p1; p1 += 1; p2 += 1; } } } statuses[i] = skill_status; }
let mut dp = vec![vec![-1; 1 << n]; m]; let size = process(&statuses, n, 0, 0, &mut dp); let mut ans = vec![0; size as usize]; let mut ansi = 0; let mut i = 0; let mut status: i32 = 0;
while status != (1 << n) - 1 { if i + 1 == m || dp[i][status as usize] != dp[i + 1][status as usize] { ans[ansi] = i as i32; ansi += 1; status |= statuses[i as usize]; } i += 1; }
ans}
fn process(people: &[i32], n: usize, i: usize, status: i32, dp: &mut Vec<Vec<i32>>) -> i32 { if status == (1 << n) - 1 { return 0; }
if i == people.len() { return i32::MAX; }
if dp[i][status as usize] != -1 { return dp[i][status as usize]; }
let p1 = process(people, n, i + 1, status, dp); let mut p2 = i32::MAX; let next2 = process(people, n, i + 1, status | people[i], dp); if next2 != i32::MAX { p2 = 1 + next2; }
let ans = p1.min(p2); dp[i][status as usize] = ans; ans}
fn main() { let req_skills = vec![ "java".to_string(), "nodejs".to_string(), "reactjs".to_string(), ]; let people = vec![ vec!["java".to_string()], vec!["nodejs".to_string()], vec!["nodejs".to_string(), "reactjs".to_string()], ]; let result = smallest_sufficient_team(req_skills, people); println!("{:?}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <unordered_map>#include <algorithm>#include <cmath>
using namespace std;
int process(const vector<int>& people, int n, int i, int status, unordered_map<int, int>& dp) { if (status == (1 << n) - 1) { return 0; } if (i == people.size()) { return INT_MAX; } int key = (i << n) | status; if (dp.find(key) != dp.end()) { return dp[key]; } int p1 = process(people, n, i + 1, status, dp); int p2 = INT_MAX; int next2 = process(people, n, i + 1, status | people[i], dp); if (next2 != INT_MAX) { p2 = 1 + next2; } int ans = min(p1, p2); dp[key] = ans; return ans;}
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) { unordered_map<string, int> skillMap; int count = 0; for (const string& skill : req_skills) { skillMap[skill] = count++; } int n = count; int m = people.size(); vector<int> statuses(m); for (int i = 0; i < m; i++) { int skillStatus = 0; const vector<string>& skills = people[i]; for (const string& skill : skills) { skillStatus |= 1 << skillMap[skill]; } statuses[i] = skillStatus; } unordered_map<int, int> dp; int size = process(statuses, n, 0, 0, dp); vector<int> ans; int i = 0, status = 0; while (status != (1 << n) - 1) { if (i + 1 == m || dp[i << n | status] != dp[(i + 1) << n | status]) { ans.push_back(i); status |= statuses[i]; } i++; } return ans;}
int main() { vector<string> req_skills = { "java", "nodejs", "reactjs" }; vector<vector<string>> people = { {"java"}, {"nodejs"}, {"nodejs", "reactjs"} };
vector<int> team = smallestSufficientTeam(req_skills, people); cout << "Team members: "; for (int member : team) { cout << member << " "; } cout << endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <string.h>
typedef struct { int* data; int size; int capacity;} IntArray;
IntArray* createIntArray() { IntArray* arr = (IntArray*)malloc(sizeof(IntArray)); arr->data = NULL; arr->size = 0; arr->capacity = 0; return arr;}
void append(IntArray* arr, int value) { if (arr->size >= arr->capacity) { int newCapacity = arr->capacity == 0 ? 1 : arr->capacity * 2; int* newData = (int*)malloc(sizeof(int) * newCapacity); if (arr->data != NULL) { memcpy(newData, arr->data, sizeof(int) * arr->size); free(arr->data); } arr->data = newData; arr->capacity = newCapacity; } arr->data[arr->size++] = value;}
void destroyIntArray(IntArray* arr) { if (arr != NULL) { if (arr->data != NULL) { free(arr->data); } free(arr); }}
int findSkillIndex(char** skills, int skillsSize, char* target) { for (int i = 0; i < skillsSize; i++) { if (strcmp(skills[i], target) == 0) { return i; } } return -1;}
void smallestSufficientTeam(char** req_skills, int req_skillsSize, char*** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnArray) { char** skills = (char**)malloc(sizeof(char*) * req_skillsSize); for (int i = 0; i < req_skillsSize; i++) { skills[i] = _strdup(req_skills[i]); }
int n = req_skillsSize; int m = peopleSize; int* statuses = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < m; i++) { int skillStatus = 0; for (int j = 0; j < peopleColSize[i]; j++) { int skillIndex = findSkillIndex(skills, req_skillsSize, people[i][j]); if (skillIndex != -1) { skillStatus |= 1 << skillIndex; } } statuses[i] = skillStatus; }
int** dp = (int**)malloc(sizeof(int*) * m); for (int i = 0; i < m; i++) { dp[i] = (int*)malloc(sizeof(int) * (1 << n)); for (int j = 0; j < (1 << n); j++) { dp[i][j] = -1; } }
int size = process(statuses, n, 0, 0, dp);
*returnSize = size; *returnArray = (int*)malloc(sizeof(int) * size); int index = 0; int i = 0; int status = 0;
while (status != (1 << n) - 1) { if (i + 1 == m || dp[i][status] != dp[i + 1][status]) { (*returnArray)[index++] = i; status |= statuses[i]; } i++; }
for (int i = 0; i < m; i++) { free(dp[i]); } free(dp);
for (int i = 0; i < req_skillsSize; i++) { free(skills[i]); } free(skills); free(statuses);}
int process(int* people, int n, int i, int status, int** dp) { if (status == (1 << n) - 1) { return 0; } if (i == n) { return INT_MAX; } if (dp[i][status] != -1) { return dp[i][status]; }
int p1 = process(people, n, i + 1, status, dp);
int p2 = INT_MAX; int next2 = process(people, n, i + 1, status | people[i], dp); if (next2 != INT_MAX) { p2 = 1 + next2; }
int ans = p1 < p2 ? p1 : p2; dp[i][status] = ans; return ans;}
int main() { char* req_skills[] = { "java", "nodejs", "reactjs" }; int req_skillsSize = sizeof(req_skills) / sizeof(req_skills[0]);
char** people[] = { (char* []) {"java"}, (char* []) {"nodejs"},(char* []) {"nodejs", "reactjs"} }; int peopleSize = sizeof(people) / sizeof(people[0]); int peopleColSize[] = { 1, 1, 2 };
int returnSize; int* returnArray;
smallestSufficientTeam(req_skills, req_skillsSize, people, peopleSize, peopleColSize, &returnSize, &returnArray);
printf("Smallest Sufficient Team:\n"); for (int i = 0; i < returnSize; i++) { printf("%d ", returnArray[i]); } printf("\n");
free(returnArray);
return 0;}
复制代码
评论