โปรแกรมหาจำนวนคอลัมน์ที่ต้องพลิกเพื่อให้แถวที่มีค่าเท่ากันมากที่สุดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี เราสามารถเลือกคอลัมน์ใดก็ได้และพลิกค่าทุกเซลล์ในคอลัมน์นั้น (0 กลายเป็น 1, 1 กลายเป็น 0) เป้าหมายคือหาจำนวนแถวสูงสุดที่มีค่าทุกเซลล์เท่ากัน (ทั้ง 0 หรือทั้ง 1) หลังจากการพลิกคอลัมน์บางส่วน

ตัวอย่าง

เมทริกซ์:

[[0, 0, 0],
 [0, 0, 1],
 [1, 1, 0]]

เอาต์พุต: 2

คำอธิบาย: พลิกคอลัมน์แรกและคอลัมน์ที่สอง แล้วแถวที่ 2 และ 3 จะกลายเป็น [1,1,1] และ [0,0,0] ตามลำดับ ทั้งสองแถวมีค่าเท่ากันทุกเซลล์

ขั้นตอนการแก้ปัญหา

1. สำหรับแต่ละแถว i ในเมทริกซ์:
   • สร้างแถวที่พลิกค่าแล้ว a โดยทำ XOR กับ 1 ทุกเซลล์
   • นับจำนวนแถว j ที่เท่ากับ i หรือเท่ากับ a
   • อัปเดตค่าสูงสุด
2. คืนค่าจำนวนสูงสุดที่พบ

เหตุผล: การพลิกคอลัมน์ทำให้แถวที่เดิมตรงกันหรือตรงข้ามกันจะกลายเป็นแถวที่เหมือนกันทุกค่า

การนำไปใช้ใน Python

class Solution(object):
    def solve(self, matrix):
        x = matrix
        m = len(matrix)
        n = len(matrix[0])
        r = 0
        for i in x:
            c = 0
            a = [l ^ 1 for l in i]
            for j in x:
                if j == i or j == a:
                    c += 1
            r = max(c, r)
        return r

ob = Solution()
matrix = [
    [0, 0, 0],
    [0, 0, 1],
    [1, 1, 0]
]
print(ob.solve(matrix))

อินพุต

[[0,0,0], [0,0,1], [1,1,0]]

เอาต์พุต

2