Lật cột để có số hàng bằng nhau tối đa trong Python

Giả sử có ma trận gồm 0 và 1, ta có thể chọn bất kỳ số cột nào và lật mọi ô trong cột đó (0 thành 1, 1 thành 0). Ta phải tìm số hàng tối đa có tất cả giá trị bằng nhau sau một số lần lật. Nếu ma trận [[0,0,0],[0,0,1],[1,1,0]], kết quả 2. Vì sau khi lật hai cột đầu, hai hàng cuối có giá trị bằng nhau.

Để giải quyết, ta làm theo các bước −

• x := matrix, m := số hàng, n := số cột, r := 0
• với mỗi hàng i trong x
  • c := 0
  • a := danh sách [l ^ 1 cho l trong i] (hàng đảo bit)
  • với mỗi hàng j trong x
    • nếu j == i hoặc j == a, tăng c 1
  • r := max(c, r)
• trả về r

Xem triển khai sau −

Ví dụ

class Solution(object):    def maxEqualRowsAfterFlips(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() print(ob.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]))

Đầu vào

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

Kết quả

2