Posted on 2023-07-16 18:16
Uriel 阅读(16)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code 、
位运算
给出需要的skill list和每个人的skill，问最少需要其中的几个人可以满足skill list里面所有skill
二进制表示skill+DP，参考Discussion -> https://leetcode.com/problems/smallest-sufficient-team/solutions/3771208/detailed-video-solution-java-python/
#1125
#Runtime: 121 ms (Beats 88.89%)
#Memory: 18.1 MB (Beats 44.44%)
class Solution(object):
def smallestSufficientTeam(self, req_skills, people):
"""
:type req_skills: List[str]
:type people: List[List[str]]
:rtype: List[int]
"""
n_p = len(people)
n_s = len(req_skills)
sk_map = {sk: i for i, sk in enumerate(req_skills)}
dp = [None] * (1 << n_s)
dp[0] = []
sk_p = []
for i in range(n_p):
t = 0
for sk in people[i]:
t |= 1 << sk_map[sk]
sk_p.append(t)
discard_p = [False] * n_p
for i in range(n_p):
for j in range(i + 1, n_p):
if (sk_p[j] | sk_p[i]) == sk_p[i]:
discard_p[j] = True
elif (sk_p[j] | sk_p[i]) == sk_p[j]:
discard_p[i] = True
for i in range(n_p):
if not discard_p[i]:
for j in range(len(dp)):
if dp[j] is None:
continue
t = j | sk_p[i]
if dp[t] is None or len(dp[j]) + 1 < len(dp[t]):
dp[t] = dp[j] + [i]
return dp[(1 << n_s) - 1]