Chương trình tìm tổng tối đa bằng cách lật từng phần tử hàng trong Python

Giả sử chúng ta có 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, chúng ta có thể lật tất cả các bit. Nếu chúng ta có thể thực hiện bất kỳ số lượng nào trong số các phép toán này và chúng ta coi mỗi hàng là một số nhị phân, chúng ta phải tìm tổng lớn nhất có thể được tạo ra từ các số này.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 11, như nếu chúng ta lật cả hai hàng, chúng ta nhận được 101 và 110, sau đó tổng là 5 + 6 =11

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đối với mỗi hàng r trong ma trận, thực hiện
  • nếu r [0] giống 0, thì
    • đối với tôi trong phạm vi từ 0 đến kích thước của r, thực hiện
      • r [i]:=-r [i] + 1
• đối với j trong phạm vi từ 1 đến kích thước cột của ma trận, thực hiện
  • cnt:=0
  • đối với tôi trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện
    • cnt:=cnt + 1 nếu ma trận [i, j] là 1 nếu không -1
  • nếu cnt <0, thì
    • đối với tôi trong phạm vi từ 0 đến kích thước hàng của ma trận, hãy thực hiện
      • ma trận [i, j]:=-matrix [i, j] + 1
• ans:=0
• đối với mỗi hàng r trong ma trận, thực hiện
  • a:=0
  • đối với mỗi v trong r, thực hiện
    • a:=2 * a + v
  • ans:=ans + a
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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