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次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告