Сложность: hard
В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.
Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.
Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.
Гарантируется, что ответ существует.
Пример:
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]
👨💻 Алгоритм:
1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.
2⃣Динамическое программирование (DP):
Создайте массив 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 и верните массив индексов людей, составляющих минимальную достаточную команду.
😎 Решение:
class 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;
}
}Ставь 👍 и забирай 📚 Базу знаний