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的空列表
键:=类似于(value,i)的映射,其中值来自req_skills,而我是数字
对于人数,通过从人员中获取人员并为其分配编号来从人员数组中获得人员对(i,p)-
total_skill:=技能组或current_skill
如果total_skill与skill_set相同,则-
如果不使用total_skill或dp[total_skill]的大小>成员的大小+1,则
忽略以下部分,跳至下一个迭代
dp[total_skill]:=成员+[i]
current_skill:=current_skill或2^key[skill]
current_skill:=0
为了技巧
对于(skill_set,members)对在dp键值对中-
returndp[(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]