1277。計算全為 1 的方形子矩陣
難度:中
主題:陣列、動態規劃、矩陣
給定一個由 1 和 0 組成的 m * n 矩陣,傳回 有多少 方 子矩陣全部為 1。
範例1:
-
輸入: 矩陣 = [[0,1,1,1], [1,1,1,1], [0,1,1,1]]
-
輸出: 15
-
說明:
- 邊長 1 有 10 個正方形。
- 邊長 2 有 4 個正方形。
- 有 1 個邊長為 3 的正方形。
- 方格總數 = 10 4 1 = 15.
範例2:
-
輸入: 矩陣 = [[1,0,1], [1,1,0], [1,1,0]]
-
輸出: 7
-
說明:
- 邊長為 1 的正方形有 6 個。
- 邊長 2 有 1 個正方形。
- 方格總數 = 6 1 = 7。
約束:
提示:
- 建立一個加法表,計算上角位於 (0,0) 的 子矩陣 的元素總和。
- 在 O(n3) 中循環所有 子方,並檢查總和是否使整個數組為 1,如果檢查結果為 1,則在答案中加 1。
解:
我們可以使用動態規劃(DP)來追蹤方子矩陣的數量,其中所有子矩陣都可以在矩陣中的每個單元格結束。以下是實現這一目標的方法:
-
DP 矩陣定義:
- 定義一個 DP 矩陣 dp,其中 dp[i][j] 表示右下角位於單元格 (i, j) 的所有子矩陣的最大方形子矩陣的大小。
-
過渡公式:
-
對於矩陣中的每個單元格 (i, j):
- 如果matrix[i][j]為1,則dp[i][j]的值取決於從(i-1,j)延伸形成的平方的最小值,(i,j -1) 和(i-1, j-1)。過渡公式為:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
登入後複製
登入後複製
- If `matrix[i][j]` is 0, `dp[i][j]` will be 0 because a square of ones cannot end at a cell with a zero.
登入後複製
-
計算所有方塊:
- 將所有 (i, j) 的 dp[i][j] 值累加,得到所有大小的方格總數。
-
時間複雜度:
- 該解決方案適用於O(m X n),其中m 和n 是矩陣的維度。
讓我們用 PHP 實作這個解:1277。計算全為 1 的方形子矩陣
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
登入後複製
登入後複製
解釋:
- 我們初始化一個二維數組 dp 來追蹤在每個位置 (i, j) 結束的最大方形子矩陣的大小。
- 對於矩陣中的每個單元:
- 如果儲存格的值為 1,我們會根據相鄰儲存格計算 dp[i][j],並將其值加入totalSquares 中。
- 最後,totalSquares 包含所有全為 1 的方形子矩陣的計數。
這個解決方案是高效的並且滿足問題中提供的限制。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是計算全為 1 的方形子矩陣的詳細內容。更多資訊請關注PHP中文網其他相關文章!