資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究用 Python 編寫的程式來查詢給定矩陣中 1 所構成的最大正方形
假設我們有一個二進位制矩陣，我們必須在該給定矩陣中找到最大的 1 正方形。
因此，如果輸入如下
| 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 |
那麼輸出將為 16。
為了解決這個問題，我們將遵循以下步驟 −
- res := 0
- 對於從 0 到矩陣大小的 i，執行以下操作
- res := res 與 matrix[i, 0] 的最大值
- 對於從 0 到 matrix[0] 大小的 i，執行以下操作
- res := res 與 matrix[0, i] 的最大值
- 對於從 1 到矩陣的行數的 i，執行以下操作
- 對於從 1 到矩陣的列數的 j，執行以下操作
- 如果 matrix[i, j] 與 1 相同，則
- matrix[i, j] = (matrix[i - 1, j], matrix[i - 1, j - 1] 和 matrix[i, j - 1]) 中的最小值加上 1
- res = res 與 matrix[i, j] 的最大值
- 如果 matrix[i, j] 與 1 相同，則
- 對於從 1 到矩陣的列數的 j，執行以下操作
- 返回 res^2
讓我們看看以下實現以獲得更好的理解 −
示例
class Solution: def solve(self, matrix): res = 0 for i in range(len(matrix)): res = max(res, matrix[i][0]) for i in range(len(matrix[0])): res = max(res, matrix[0][i]) for i in range(1, len(matrix)): for j in range(1, len(matrix[0])): if matrix[i][j] == 1: matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1 res = max(res, matrix[i][j]) return res * res ob = Solution() matrix = [ [1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 1], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0] ] print(ob.solve(matrix))
輸入
matrix = [ [1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 1], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0] ]
輸出
16
更新於： 2020 年 12 月 2 日
636 次瀏覽
廣告