Nhóm đủ nhỏ nhất ở Pyhton

Giả sử đối với một dự án chúng ta có một danh sách các kỹ năng bắt buộc được gọi là req_skills và một danh sách những người. Ở đây những người thứ i [i] chứa danh sách các kỹ năng mà người đó có.

Bây giờ, giả sử một nhóm đủ được định nghĩa là một tập hợp những người sao cho đối với mỗi kỹ năng bắt buộc trong req_skills, có ít nhất một người trong nhóm có kỹ năng đó. Chúng ta có thể đại diện cho các nhóm này theo chỉ số của mỗi người:Ví dụ, giả sử nhóm là [0, 1, 3], chỉ số này đại diện cho những người có kỹ năng, người [0], người [1] và người [3].

Chúng tôi phải tìm đội có quy mô nhỏ nhất có thể.

Bạn có thể trả lại câu trả lời theo bất kỳ thứ tự nào. Nó được đảm bảo rằng một câu trả lời tồn tại.

Vì vậy, nếu đầu vào giống như req_skills =["java", "flashing", "android"], people =[["java"], ["android"], ["flashing", "android"]], thì đầu ra sẽ là [0,2]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• dp:=một bản đồ, thêm danh sách trống tương ứng với phím 0

• key:=một bản đồ như (value, i) trong đó giá trị là từ req_skills và i là số

• cho số, cặp người (i, p) từ mảng người bằng cách lấy người và gán số cho họ -

  • current_skill:=0

  • để có kỹ năng trong p

    • current_skill:=current_skill HOẶC 2 ^ phím [kỹ năng]

  • cặp for (skill_set, Member) nằm trong cặp khóa-giá trị dp -

    • total_skill:=skill_set HOẶC current_skill

    • nếu total_skill giống với skill_set thì -

      • Bỏ qua phần sau, chuyển sang phần tiếp theo

    • nếu total_skill không hoạt động hoặc kích thước dp [total_skill]> kích thước thành viên +1, thì

      • dp [total_skill]:=thành viên + [i]

• return dp [(1 <

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"]]))

Đầu vào

["java","flutter","android"]
[["java"],["android"],["flutter","android"]]

Đầu ra

[0,2]