สมมติว่าเรามีรายการสี (R, G, B) ถ้าสีต่างกันอยู่ติดกัน สามารถรวมกลายเป็นสีที่สามได้ ต้องการหาจำนวนสีที่เหลือน้อยที่สุดหลังทำการรวมอย่างใดอย่างหนึ่ง
เช่น colors = ["G", "R", "G", "B", "R"] ผลลัพธ์ = 1 สามารถรวมได้จนเหลือ 1 สี
ขั้นตอนการแก้ปัญหา (XOR Properties)
n := len(colors)- ถ้ามีสีเพียงสีเดียว คืน
n - ถ้า
n <= 1คืนn x := 0,d := {"R": 1, "G": 2, "B": 3}- วนทุก
cในcolors:x ^= d[c] - คืน
2 if x == 0 else 1
เหตุผล: การแทนสีด้วย 1,2,3 และ XOR ทั้งหมด จะได้ invariant ของระบบ
ตัวอย่างโค้ด
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
