โปรแกรมค้นหาสีตัวเลขขั้นต่ำยังคงอยู่หลังจากรวมใน Python

สมมติว่าเรามีรายการสี (R, G, B) ตอนนี้ ถ้ามีสีที่ต่างกันสองสีอยู่ติดกัน พวกมันก็สามารถแปลงเป็นรายการสีเดียวของสีที่สามได้ เราต้องหาจำนวนที่น้อยที่สุดที่เหลืออยู่หลังจากลำดับของการแปลงใดๆ ที่เป็นไปได้

ดังนั้น หากอินพุตเป็นสี =["G", "R", "G", "B", "R"] ผลลัพธ์จะเป็น 1 เนื่องจากสามารถแปลงได้ดังรูปด้านล่าง -

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของสี
• ถ้าสีมีสีต่างกันเพียงสีเดียว
  • ส่งคืน n
• ถ้า n <=1 แล้ว
  • ส่งคืน n
• x :=0
• d :=แผนที่ที่มีค่าคีย์คู่ {("R", 1), ("G", 2), ("B", 3)}
• สำหรับแต่ละสี c ทำ
  • x :=x XOR d[c]
• ส่งกลับ 2 ถ้า x เหมือนกับ 0 มิฉะนั้น 1

ตัวอย่าง (Python)

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

class Solution:
   def solve(self, colors):
      n = len(colors)
      if len(set(colors)) == 1:
         return n
      if n <= 1:
         return n
      x = 0
      d = {"R": 1, "G": 2, "B": 3}
      for qux in colors:
         x ^= d[qux]
      return 2 if x == 0 else 1   
ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))

อินพุต

["G", "R", "G", "B", "R"]

ผลลัพธ์

1