Chương trình tìm tổng lớn nhất bằng cách lật bit từng hàng trong Python

Cho một ma trận nhị phân 2D. Đối với bất kỳ hàng hoặc cột nào trong ma trận cho trước, chúng ta có thể lật tất cả các bit (0 thành 1, 1 thành 0). Nếu có thể thực hiện bất kỳ số lượng phép toán nào, và coi mỗi hàng như một số nhị phân, hãy tìm tổng lớn nhất có thể đạt được từ các số này.

Ví dụ, nếu đầu vào là:

Thì đầu ra sẽ là 11, vì nếu lật cả hai hàng ta được 101 và 110, tổng là 5 + 6 = 11.

Để giải quyết, thực hiện các bước sau:

• Với mỗi hàng r trong ma trận:
  • Nếu r[0] == 0, lật toàn bộ hàng: r[i] = -r[i] + 1 cho mọi i.
• Với mỗi cột j từ 1 đến số cột - 1:
  • Đếm cnt = số lượng 1 trừ số lượng 0 trong cột j.
  • Nếu cnt < 0, lật toàn bộ cột j.
• Tính tổng: với mỗi hàng, chuyển dãy bit thành số nguyên và cộng dồn.
• Trả về tổng.

Ví dụ triển khai

class Solution:
    def solve(self, matrix):
        for r in matrix:
            if r[0] == 0:
                for i in range(len(r)):
                    r[i] = -r[i] + 1
        
        for j in range(1, len(matrix[0])):
            cnt = 0
            for i in range(len(matrix)):
                cnt += 1 if matrix[i][j] else -1
            if cnt < 0:
                for i in range(len(matrix)):
                    matrix[i][j] = -matrix[i][j] + 1
        
        ans = 0
        for r in matrix:
            a = 0
            for v in r:
                a = 2 * a + v
            ans += a
        return ans

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

Đầu vào

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

Đầu ra

11