数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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]
255 次浏览
