Chương trình tìm số màu tối thiểu còn lại sau khi hợp nhất trong Python

Cho danh sách màu (R, G, B). Nếu hai màu khác nhau liền kề, chúng hợp thành màu thứ ba. Tìm số lượng màu tối thiểu có thể còn lại sau các phép hợp nhất.

Ví dụ: ["G","R","G","B","R"] → có thể giảm xuống 1 màu.

Giải thuật (XOR trên mã hóa màu)

Mã hóa: R=1, G=2, B=3. XOR của tất cả các mã cho ra giá trị x.

• Nếu chỉ có 1 màu duy nhất → trả về n.
• Nếu n <= 1 → trả về n.
• Tính x = XOR của tất cả mã màu.
• Nếu x == 0 → trả về 2, ngược lại trả về 1.

Điều này xuất phát từ tính chất bất biến của phép XOR dưới phép hợp nhất.

Mã nguồn 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 c in colors:
            x ^= d[c]
        return 2 if x == 0 else 1

ob = Solution()
colors = ["G", "R", "G", "B", "R"]
print(ob.solve(colors))  # Output: 1

Đầu vào

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

Đầu ra

1