ทีมพอเพียงที่เล็กที่สุดใน Pyhton

สมมติว่าสำหรับโปรเจ็กต์ เรามีรายชื่อทักษะที่จำเป็นที่เรียกว่า req_skills และรายชื่อบุคคล ที่นี่ i-th people 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) โดยที่ค่ามาจาก req_skills และฉันคือตัวเลข

• สำหรับหมายเลข คู่บุคคล (i, p) จากอาร์เรย์บุคคลโดยรับบุคคลและกำหนดหมายเลขให้กับพวกเขา −

  • current_skill :=0

  • สำหรับความชำนาญใน p

    • current_skill :=current_skill หรือ 2^key[skill]

  • สำหรับคู่ (skill_set,members) อยู่ในคู่คีย์-ค่า dp -

    • Total_skill :=skill_set หรือ current_skill

    • ถ้า total_skill เหมือนกับ skill_set แล้ว −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • ถ้า total_skill ไม่อยู่ใน do หรือขนาด dp[total_skill]> ขนาดของสมาชิก + 1 แล้ว

      • dp[total_skill] :=สมาชิก + [i]

• ส่งคืน dp[(1 <

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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]