使用Python統計全為1的子矩陣個數的程式

假設我們有一個m x n的二進位制矩陣，我們需要找到有多少個子矩陣全為1。

例如，如果輸入是：

101
011
011

那麼輸出將是13，因為有6個(1x1)矩陣，3個(2x1)矩陣，2個(1x2)矩陣，1個(3x1)矩陣和1個(4x4)矩陣。

為了解決這個問題，我們將遵循以下步驟：

  • m := 矩陣的行數

  • n := 矩陣的列數

  • dp := 一個大小相同的m x n的零矩陣

  • 對於 i 從 0 到 m - 1：

    • 對於 j 從 0 到 n - 1：

      • 如果 i 等於 0 且 matrix[i, j] 為1，則：

        • dp[i, j] := 1

      • 否則，如果 matrix[i][j] 不為零，則：

        • dp[i, j] := dp[i-1, j] + 1

  • total := 0

  • 對於 i 從 0 到 m - 1：

    • 對於 j 從 0 到 n - 1：

      • 對於 k 從 j+1 到 n：

        • total := total + dp[i,j] 到 dp[i,k] 的最小值

  • 返回 total

讓我們來看下面的實現來更好地理解：

示例

線上演示

def solve(matrix):
   m = len(matrix)
   n = len(matrix[0])
   dp = [[0] * n for _ in range(m)]
   for i in range(m):
      for j in range(n):
         if i == 0 and matrix[i][j]:
            dp[i][j] = 1
         elif matrix[i][j]:
            dp[i][j] = dp[i-1][j] + 1
   total = 0
   for i in range(m):
      for j in range(n):
         for k in range(j+1, n+1):
            total += min(dp[i][j:k])
   return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

輸入

[4,6,7,8], 11

輸出

13

更新於：2021年5月29日

524 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告