Python程序：翻转每一行元素以查找最大和

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

因此，如果输入类似于：

010
001

则输出将为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，否则cnt := cnt - 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))

输入

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

输出

11

更新于：2020年11月19日

197次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告