[Swift]LeetCode1125.最小的必要团队|SmallestSufficientTeam

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。

我们可以用每个人的编号来表示团队中的成员：例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，本题保证答案存在。

示例 1：

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

示例 2：

输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]

提示：

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
req_skills 和 people[i] 中的元素分别各不相同
req_skills[i][j], people[i][j][k] 都由小写英文字母组成
本题保证「必要团队」一定存在

132ms

 1 class Solution {
 2     func smallestSufficientTeam(_ req_skills: [String], _ people: [[String]]) -> [Int] {
 3         var solution = Set<Int>()
 4         var setPeople = people.map { Set($0) }
 5         var skillToPeopleDict = [String:[Int]]()
 6         
 7         for (i, personSet) in setPeople.enumerated() {
 8             for (j, anotherPersonSet) in setPeople.enumerated() where i != j {
 9                 if personSet.isSubset(of: anotherPersonSet) {
10                     setPeople[i] = []
11                     break
12                 }
13             }
14         }
15         
16         for (i, personSet) in setPeople.enumerated() {
17             for skill in personSet {
18                 skillToPeopleDict[skill] = (skillToPeopleDict[skill] ?? []) + [i]
19             }
20         }
21         
22         return smallestSufficientTeam(req_skills, skillToPeopleDict, setPeople, 0, [], [])
23     }
24     
25     func smallestSufficientTeam(_ skills: [String], 
26                                 _ skillToPeopleDict: [String:[Int]],
27                                 _ people: [Set<String>],
28                                 _ i: Int,
29                                 _ totalSkillsAdded: Set<String>,
30                                 _ soFar: [Int]) -> [Int] {
31         if i >= skills.count { return Array(soFar) }
32         
33         let nextSkill = skills[i]
34         
35         if totalSkillsAdded.contains(nextSkill) {
36             return smallestSufficientTeam(skills, skillToPeopleDict, people, i+1, totalSkillsAdded, soFar)   
37         }
38         
39         var solution = [Int]()
40         
41         for person in skillToPeopleDict[nextSkill] ?? [] {
42             let personSkills = people[person]
43             let next = smallestSufficientTeam(skills, 
44                                               skillToPeopleDict, 
45                                               people, 
46                                               i+1, 
47                                               totalSkillsAdded.union(personSkills),
48                                               soFar + [person])   
49             
50             if !next.isEmpty {
51                 if solution.isEmpty {
52                     solution = next
53                 } else if next.count < solution.count {
54                     solution = next
55                 }
56             }
57         }
58         
59         return solution
60     }
61 }

156ms

 1 class Solution {
 2     func smallestSufficientTeam(_ req_skills: [String], _ people: [[String]]) -> [Int] {
 3         let req_skills_len = req_skills.count, people_len = people.count
 4         var map = [String: Int]()
 5         for i in 0..<req_skills_len {
 6             map[req_skills[i]] = i
 7         }
 8         var dp = [Int: [Int]]()
 9         dp[0] = [Int]()
10 
11         for i in 0..<people_len {
12             var his_skill = 0
13             for skill in people[i] {
14                 if map[skill] != nil {
15                     his_skill |= 1<<map[skill]!
16                 }
17             }
18             for (skill_set, need) in dp {
19                 let with_him = skill_set | his_skill
20                 if with_him == skill_set { continue }
21                 if dp[with_him] == nil || dp[with_him]!.count > need.count+1 {
22                     var sets = need
23                     sets.append(i)
24                     dp[with_him] = sets
25                 }
26             }
27         }
28         return dp[1<<req_skills_len - 1, default: [Int]()]
29     }
30 }

180ms

 1 class Solution {
 2     func smallestSufficientTeam(_ req_skills: [String], _ people: [[String]]) -> [Int] {
 3         let n = req_skills.count 
 4         let m = people.count 
 5         var dict = [String: Int]()
 6         for i in 0..<req_skills.count {
 7             let skill = req_skills[i]
 8             dict[skill] = i
 9         }
10         
11         var dp = [Int: [Int]]()
12         dp[0] = [Int]()
13         
14         for (idx, skills) in people.enumerated() {
15             var his_skill = 0
16             for skill in skills {
17                 his_skill |= 1 << dict[skill]!
18             }
19             
20             for (skill_set, need) in dp {
21                 let with_him = skill_set | his_skill
22                 if with_him == skill_set { continue }
23                 if dp[with_him] == nil || dp[with_him]!.count > need.count + 1 {
24                     dp[with_him] = need + [idx]
25                 }
26             }
27         }
28         return dp[(1<<n) - 1]!
29     }
30 }

296ms

 1 class Solution {
 2     struct Team {
 3         public let people: [Int]
 4           public let required: Set<String>
 5 
 6         init(required: [String]) {
 7              self.people = []
 8                self.required = Set<String>(required)
 9         }
10 
11         init(team: Team, adding idx: Int, with skills: [String]) {
12             self.people = team.people + [ idx ]
13                self.required = team.required.subtracting(skills)
14         }
15     }
16 
17     private func completeTeam(_ team: Team, _ people: [[String]], _ bySkill: [String:[Int]]) -> Team? {
18         guard let skill = team.required.first else {
19             return team
20         }
21         guard let withSkill = bySkill[skill] else {
22             return nil
23         }
24 
25         var bestTeam: Team?
26         var requiredUsed = Set<Set<String>>()
27         for idx in withSkill {
28             let tmpTeam = Team(team: team, adding: idx, with: people[idx])
29             if requiredUsed.contains(tmpTeam.required) {
30                 continue
31             }
32             requiredUsed.insert(tmpTeam.required)
33             
34             guard let tmpResult = self.completeTeam(tmpTeam, people, bySkill) else {
35                 continue
36             }
37             if bestTeam == nil || bestTeam!.people.count > tmpResult.people.count {
38                 bestTeam = tmpResult
39             }
40         }
41         return bestTeam
42     }
43 
44     func smallestSufficientTeam(_ req_skills: [String], _ people: [[String]]) -> [Int] {
45         guard req_skills.count > 0 && people.count > 0 else {
46             return []
47         }
48 
49         var bySkill = [String:[Int]]()
50         let team = Team(required: req_skills)
51         for (idx, skills) in people.enumerated() {
52             for skill in team.required.intersection(skills) {
53                   bySkill[skill, default: []].append(idx)
54             }
55         }
56 
57         if let result = self.completeTeam(team, people, bySkill) {
58             return result.people
59         } else {
60             return []
61         }
62     }
63 }

Runtime: 652 ms

Memory Usage: 82.7 MB

 1 class Solution {
 2     func smallestSufficientTeam(_ req_skills: [String], _ people: [[String]]) -> [Int] {
 3         var inf:Int = 0x3f3f3f3f
 4         let m:Int = req_skills.count
 5         let n:Int = people.count
 6         var all:Int = 1 << m
 7         var skill_id:[String:Int] = [String:Int]()
 8         var k:Int = 0
 9         for skill in req_skills
10         {
11             skill_id[skill] = k
12             k += 1
13         }
14         var skillset:[Int] = [Int](repeating:0,count:n)
15         for i in 0..<n
16         {
17             var st:Int = 0
18             for skill in people[i]
19             {
20                 st |= 1 << skill_id[skill]!
21             }
22             skillset[i] = st
23         }
24         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:inf,count:all),count:n + 1)
25         var last:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:all),count:n + 1)
26         dp[0][0] = 0
27         for i in 1...n
28         {
29             for j in 0..<all
30             {
31                 if dp[i][j] > dp[i - 1][j]
32                 {
33                     dp[i][j] = dp[i - 1][j]
34                     last[i][j] = j
35                 }
36                 if dp[i - 1][j] + 1 < dp[i][j | skillset[i - 1]]
37                 {
38                     dp[i][j | skillset[i - 1]] = dp[i - 1][j] + 1
39                     last[i][j | skillset[i - 1]] = j
40                 }
41             }
42         }
43         var i:Int = n
44         var j:Int = all - 1
45         var res:[Int] = [Int]()
46         while(i != 0)
47         {
48             if last[i][j] != j
49             {
50                 res.insert(i - 1,at:0)
51             }
52             j = last[i][j]
53             i -= 1
54         }
55         return res      
56     }
57 }