Python 最小充分团队

假设一个项目需要一组技能列表 `req_skills`，以及一个人员列表 `people`。其中，第 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 是数字

• 对于来自 `people` 数组的人员对 (i, p) (通过获取人员并为其分配编号):

  • current_skill := 0

  • 对于 p 中的每个技能:

    • current_skill := current_skill OR 2^key[skill]

  • 对于 dp 键值对中的 (skill_set,members) 对:

    • total_skill := skill_set OR current_skill

    • 如果 total_skill 与 skill_set 相同，则：

      • 忽略以下部分，跳到下一个迭代

    • 如果 total_skill 不在 dp 中或 dp[total_skill] 的大小 > members + 1 的大小，则

      • dp[total_skill] := members + [i]

• 返回 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]

Arnab Chakraborty

更新于：2020年6月4日

255 次浏览

开启你的职业生涯

通过完成课程获得认证

开始