Pyhton 中最小的充分团队
假设对于一个项目，我们有一个名为 req_skills 的所需技能列表和人员列表。这里第 i 个人 people[i] 包含该人拥有的技能列表。
现在假设一个充分团队被定义为一组人员，对于 req_skills 中的每项所需技能，团队中至少有一个人拥有该技能。我们可以用每个人的索引来表示这些团队:例如，假设团队为 [0, 1, 3]，这代表具有技能 people[0]、people[1] 和 people[3] 的人员。
我们必须找到尽可能小的团队。
您可以按任何顺序返回答案。保证存在答案。
因此，如果输入为 req_skills = ["java","flutter","android"], people = [["java"],["android"],["flutter","android"]]，则输出为 [0,2]
要解决这个问题，我们将遵循以下步骤 −
dp := 一个映射，添加与键 0 对应的空列表
key := 一个类似 (value,i) 的映射，其中 value 来自 req_skills，i 是数字
对于 number,person 对 (i, p)，从 people 数组中获取 people 并为其分配数字 −
current_skill := 0
for skill in p
current_skill := current_skill OR 2^key[skill]
for (skill_set,members) 对在 dp 键值对中 −
total_skill := skill_set OR current_skill
如果 total_skill 与 skill_set 相同，则 −
忽略以下部分，跳到下一次迭代
如果 total_skill 不在 do 中或 dp[total_skill] 的大小 >成员大小 + 1，然后
dp[total_skill] := members + [i]
return dp[(1 << len(req_skills))
让我们看看下面的实现以便更好地理解 −
示例
class Solution(object):
def smallestSufficientTeam(self, req_skills, people):
dp = {0:[]}
key = {v:i for i,v in enumerate(req_skills)}
for i,p in enumerate(people):
current_skill = 0
for skill in p:
current_skill |= 1<< key[skill]
for skill_set, members in dp.items():
total_skill = skill_set|current_skill
if total_skill == skill_set:
continue
if total_skill not in dp or len(dp[total_skill])>
len(members)+1:
dp[total_skill] = members + [i]
return dp[(1<<len(req_skills)) - 1]
ob = Solution()
print(ob.smallestSufficientTeam(["java","flutter","android"],
[["java"],["android"],["flutter","android"]]))
输入
["java","flutter","android"] [["java"],["android"],["flutter","android"]]
输出
[0,2]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
