資料結構
網路
關係資料庫管理系統 (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 次瀏覽
