用 Python 编写一个通过翻转每行元素来查找最大和的程序

pythonserver side programmingprogramming

假设我们有一个 2D 二进制矩阵。对于给定矩阵中的任何行或列，我们都可以翻转所有位。如果我们可以执行任意数量的这些操作，并且我们将每一行视为二进制数，那么我们必须找到这些数字可以组成的最大和。

因此，如果输入如下

0	1	0
0	0	1

那么输出将是 11，因为如果我们翻转两行，我们得到 101 和 110，那么总和是 5 + 6 = 11

为了解决这个问题，我们将遵循以下步骤 −

对于矩阵中的每一行 r，执行
- 如果 r[0] 与 0 相同，那么
  - 对于范围在 0 到 r 的大小内的 i，执行
    - r[i] := -r[i] + 1
对于范围在 1 到矩阵的列大小内的 j，执行
- cnt := 0
- 对于范围在 0 到矩阵的行数内的 i，执行
  - 如果 matrix[i, j] 为 1，则 cnt := cnt + 1，否则为 -1
- 如果 cnt < 0，则
  - 对于范围从 0 到矩阵行大小的 i，执行
    - matrix[i, j] := -matrix[i, j] + 1
ans := 0
对于矩阵中的每一行 r，执行
- a := 0
- 对于 r 中的每个 v，执行
  - a := 2 * a + v
- ans := ans + a
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

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))