2023-09-10：用go語言編寫。作為項(xiàng)目經(jīng)理，你規(guī)劃了一份需求的技能清單 req_skills，

并打算從備選人員名單 people 中選出些人組成一個(gè)「必要團(tuán)隊(duì)」

（ 編號(hào)為 i 的備選人員 people[i] 含有一份該備選人員掌握的技能列表）。

所謂「必要團(tuán)隊(duì)」，就是在這個(gè)團(tuán)隊(duì)中，

對(duì)于所需求的技能列表 req_skills 中列出的每項(xiàng)技能，

團(tuán)隊(duì)中至少有一名成員已經(jīng)掌握。可以用每個(gè)人的編號(hào)來表示團(tuán)隊(duì)中的成員：

例如，團(tuán)隊(duì) team = [0, 1, 3] 表示掌握技能分別為

people[0]，people[1]，和 people[3] 的備選人員。

請(qǐng)你返回 任一 規(guī)模最小的必要團(tuán)隊(duì)，團(tuán)隊(duì)成員用人員編號(hào)表示。

你可以按 任意順序 返回答案，題目數(shù)據(jù)保證答案存在。

輸入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]。

輸出：[0,2]。

來自左程云。

答案2023-09-10：

大體步驟如下：

1.首先，我們對(duì) reqSkills 進(jìn)行排序，獲得排序后的技能列表。這是為了后續(xù)方便進(jìn)行比較。例如，將 ["java", "nodejs", "reactjs"] 排序?yàn)?["java", "nodejs", "reactjs"]。

2.初始化變量 n 為 reqSkills 的長(zhǎng)度，變量 m 為 people 的長(zhǎng)度，并創(chuàng)建一個(gè)長(zhǎng)度為 m 的整數(shù)數(shù)組 statuses 用于記錄每個(gè)人的技能狀態(tài)。

3.對(duì)于每個(gè)人，我們通過比較技能列表和排序后的 reqSkills 列表，來確定他們掌握的技能狀態(tài)。首先，將該人的技能列表排序。然后使用雙指針法，一個(gè)指針指向排序后的 reqSkills 列表，另一個(gè)指針指向該人的技能列表。比較兩個(gè)指針指向的技能，如果相等，則表示該人掌握了該技能，將對(duì)應(yīng)的狀態(tài)位置為1，并將兩個(gè)指針都向后移動(dòng)一位；如果 reqSkills[p1] 小于 skill[p2]，則將指向 reqSkills 的指針向后移動(dòng)一位；否則將指向技能列表的指針向后移動(dòng)一位。重復(fù)這個(gè)過程直到其中一個(gè)指針超出范圍。

4.將每個(gè)人的技能狀態(tài)記錄在 statuses 數(shù)組中。

5.創(chuàng)建一個(gè)二維數(shù)組 dp，其中 dp[i][j] 表示從第 i 個(gè)人開始，技能狀態(tài)為 j 時(shí)，所需的最小團(tuán)隊(duì)人數(shù)。初始化 dp 數(shù)組的所有元素為 -1。

6.調(diào)用遞歸函數(shù) process，該函數(shù)的參數(shù)包括：people 數(shù)組，技能列表的長(zhǎng)度 n，當(dāng)前處理的人員下標(biāo) i，當(dāng)前的技能狀態(tài) status，以及 dp 數(shù)組。

7.在遞歸函數(shù) process 中，首先判斷當(dāng)前技能狀態(tài)是否已經(jīng)滿足所有需求，即 status 是否等于 (1<<n)-1。如果滿足，則返回0表示不需要再增加人員。

8.接下來，判斷是否已經(jīng)遍歷了所有人員，即 i 是否等于 people 數(shù)組的長(zhǎng)度。如果是，說明無法滿足所有需求，并返回一個(gè)較大的值，這里使用 1<<31-1 來表示無窮大。

9.然后，判斷 dp 數(shù)組中是否已經(jīng)記錄了當(dāng)前人員和技能狀態(tài)的最小團(tuán)隊(duì)人數(shù)，如果是，直接返回該值。

10.在遞歸函數(shù)中，我們有兩個(gè)遞歸調(diào)用，第一個(gè)是繼續(xù)嘗試從下一個(gè)人員開始不增加人員的情況，即調(diào)用 process(people, n, i+1, status, dp)，將返回的值保存在變量 p1 中。

11.第二個(gè)遞歸調(diào)用是嘗試從下一個(gè)人員開始增加當(dāng)前人員的情況，即調(diào)用 process(people, n, i+1, status|people[i], dp)，將返回的值保存在變量 p2 中。注意，這里的參數(shù) status|people[i] 表示將當(dāng)前人員的技能狀態(tài)添加到當(dāng)前技能狀態(tài)中。

12.如果 p2 不等于 1<<31-1，說明可以滿足當(dāng)前需求，將 p2+1 指代的團(tuán)隊(duì)人數(shù)保存在變量 ans 中，否則將 ans 設(shè)置為 p1。

13.將 ans 保存在 dp 數(shù)組中以便下次使用，并返回 ans。

14.在主函數(shù)中，根據(jù)返回的最小團(tuán)隊(duì)人數(shù) size，創(chuàng)建一個(gè)大小為 size 的整數(shù)數(shù)組 ans 和一個(gè)指示 ans 數(shù)組下標(biāo)的變量 ansi。

15.初始化變量 i 為0，status 為0，用于記錄當(dāng)前處理的人員下標(biāo)和技能狀態(tài)。

16.如果 status 不等于 (1<<n)-1，即還沒有滿足所有需求，執(zhí)行循環(huán)。在循環(huán)中，判斷兩個(gè)條件：如果 i+1 等于 m，說明已經(jīng)遍歷到了最后一個(gè)人員；如果 dp[i][status] 不等于 dp[i+1][status]，表示從當(dāng)前人員開始增加人員可以滿足當(dāng)前需求。

17.如果滿足上述兩個(gè)條件之一，將 i 添加到 ans 數(shù)組中，并將 ansi 自增1。然后將當(dāng)前人員的技能狀態(tài)添加到當(dāng)前技能狀態(tài)中。

18.無論是否滿足條件，將 i 自增1。

19.執(zhí)行完循環(huán)后，返回 ans 數(shù)組作為結(jié)果。

總的時(shí)間復(fù)雜度為O(m * (2^n))，額外空間復(fù)雜度為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;
}