1125. Smallest Sufficient Team
В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.
Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.
НаVí dụ, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
return любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.
Гарантируется, что ответ существует.
Ví dụ:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]
C# lời giải
đã khớp/gốcpublic class Solution {
public int[] SmallestSufficientTeam(string[] req_skills, IList<IList<string>> people) {
int n = people.Count, m = req_skills.Length;
var skillId = new Dictionary<string, int>();
for (int i = 0; i < m; i++) {
skillId[req_skills[i]] = i;
}
var skillsMaskOfPerson = new int[n];
for (int i = 0; i < n; i++) {
foreach (var skill in people[i]) {
if (skillId.ContainsKey(skill)) {
skillsMaskOfPerson[i] |= 1 << skillId[skill];
}
}
}
var dp = new long[1 << m];
Array.Fill(dp, (1L << n) - 1);
dp[0] = 0;
for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
for (int i = 0; i < n; i++) {
int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
if (smallerSkillsMask != skillsMask) {
long peopleMask = dp[smallerSkillsMask] | (1L << i);
if (BitCount(peopleMask) < BitCount(dp[skillsMask])) {
dp[skillsMask] = peopleMask;
}
}
}
}
long answerMask = dp[(1 << m) - 1];
var ans = new List<int>();
for (int i = 0; i < n; i++) {
if (((answerMask >> i) & 1) == 1) {
ans.Add(i);
}
}
return ans.ToArray();
}
private int BitCount(long value) {
int count = 0;
while (value != 0) {
value &= (value - 1);
count++;
}
return count;
}
}C++ lời giải
bản nháp tự động, xem lại trước khi gửi#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int>& SmallestSufficientTeam(vector<string> req_skills, IList<vector<string>> people) {
int n = people.size(), m = req_skills.size();
var skillId = new unordered_map<string, int>();
for (int i = 0; i < m; i++) {
skillId[req_skills[i]] = i;
}
var skillsMaskOfPerson = new int[n];
for (int i = 0; i < n; i++) {
foreach (var skill in people[i]) {
if (skillId.count(skill)) {
skillsMaskOfPerson[i] |= 1 << skillId[skill];
}
}
}
var dp = new long[1 << m];
Array.Fill(dp, (1L << n) - 1);
dp[0] = 0;
for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
for (int i = 0; i < n; i++) {
int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
if (smallerSkillsMask != skillsMask) {
long peopleMask = dp[smallerSkillsMask] | (1L << i);
if (BitCount(peopleMask) < BitCount(dp[skillsMask])) {
dp[skillsMask] = peopleMask;
}
}
}
}
long answerMask = dp[(1 << m) - 1];
var ans = new List<int>();
for (int i = 0; i < n; i++) {
if (((answerMask >> i) & 1) == 1) {
ans.push_back(i);
}
}
return ans.ToArray();
}
private int BitCount(long value) {
int count = 0;
while (value != 0) {
value &= (value - 1);
count++;
}
return count;
}
}Java lời giải
đã khớp/gốcclass Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
int n = people.size(), m = req_skills.length;
HashMap<String, Integer> skillId = new HashMap<String, Integer>();
for (int i = 0; i < m; i++) {
skillId.put(req_skills[i], i);
}
int skillsMaskOfPerson[] = new int[n];
for (int i = 0; i < n; i++) {
for (String skill : people.get(i)) {
skillsMaskOfPerson[i] |= 1 << skillId.get(skill);
}
}
long dp[] = new long [1 << m];
Arrays.fill(dp, (1L << n) - 1);
dp[0] = 0;
for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
for (int i = 0; i < n; i++) {
int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
if (smallerSkillsMask != skillsMask) {
long peopleMask = dp[smallerSkillsMask] | (1L << i);
if (Long.bitCount(peopleMask) < Long.bitCount(dp[skillsMask])) {
dp[skillsMask] = peopleMask;
}
}
}
}
long answerMask = dp[(1 << m) - 1];
int ans[] = new int [Long.bitCount(answerMask)];
int ptr = 0;
for (int i = 0; i < n; i++) {
if (((answerMask >> i) & 1) == 1) {
ans[ptr++] = i;
}
}
return ans;
}
}JavaScript lời giải
đã khớp/gốcvar smallestSufficientTeam = function(req_skills, people) {
const n = people.length, m = req_skills.length;
const skillId = new Map(req_skills.map((skill, i) => [skill, i]));
const skillsMaskOfPerson = Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (const skill of people[i]) {
if (skillId.has(skill)) {
skillsMaskOfPerson[i] |= 1 << skillId.get(skill);
}
}
}
const dp = Array(1 << m).fill((1 << n) - 1);
dp[0] = 0;
for (let skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
for (let i = 0; i < n; i++) {
const smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
if (smallerSkillsMask !== skillsMask) {
const peopleMask = dp[smallerSkillsMask] | (1 << i);
if (bitCount(peopleMask) < bitCount(dp[skillsMask])) {
dp[skillsMask] = peopleMask;
}
}
}
}
const answerMask = dp[(1 << m) - 1];
const result = [];
for (let i = 0; i < n; i++) {
if ((answerMask >> i) & 1) {
result.push(i);
}
}
return result;
};
function bitCount(n) {
let count = 0;
while (n) {
count += n & 1;
n >>= 1;
}
return count;
}Python lời giải
đã khớp/gốcclass Solution:
def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
n = len(people)
m = len(req_skills)
skillId = {skill: i for i, skill in enumerate(req_skills)}
skillsMaskOfPerson = [0] * n
for i in range(n):
for skill in people[i]:
if skill in skillId:
skillsMaskOfPerson[i] |= 1 << skillId[skill]
dp = [(1 << n) - 1] * (1 << m)
dp[0] = 0
for skillsMask in range(1, 1 << m):
for i in range(n):
smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i]
if smallerSkillsMask != skillsMask:
peopleMask = dp[smallerSkillsMask] | (1 << i)
if bin(peopleMask).count('1') < bin(dp[skillsMask]).count('1'):
dp[skillsMask] = peopleMask
answerMask = dp[(1 << m) - 1]
return [i for i in range(n) if (answerMask >> i) & 1]Go lời giải
đã khớp/gốcimport "math/bits"
func smallestSufficientTeam(req_skills []string, people [][]string) []int {
n, m := len(people), len(req_skills)
skillId := make(map[string]int)
for i, skill := range req_skills {
skillId[skill] = i
}
skillsMaskOfPerson := make([]int, n)
for i, person := range people {
for _, skill := range person {
if id, ok := skillId[skill]; ok {
skillsMaskOfPerson[i] |= 1 << id
}
}
}
dp := make([]int64, 1<<m)
for i := range dp {
dp[i] = (1 << n) - 1
}
dp[0] = 0
for skillsMask := 1; skillsMask < (1 << m); skillsMask++ {
for i := 0; i < n; i++ {
smallerSkillsMask := skillsMask &^ skillsMaskOfPerson[i]
if smallerSkillsMask != skillsMask {
peopleMask := dp[smallerSkillsMask] | (1 << i)
if bits.OnesCount64(uint64(peopleMask)) < bits.OnesCount64(uint64(dp[skillsMask])) {
dp[skillsMask] = peopleMask
}
}
}
}
answerMask := dp[(1<<m)-1]
result := []int{}
for i := 0; i < n; i++ {
if (answerMask>>i)&1 == 1 {
result = append(result, i)
}
}
return result
}Algorithm
1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте mảng skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.
2⃣dynamic programming (DP):
Создайте mảng dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).
3⃣Формирование ответа:
Извлеките ответ из dp и return mảng индексов людей, составляющих минимальную достаточную команду.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.