数据结构
网络
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 次浏览
广告