如何在一个由0和1组成的矩阵中找到由1组成的最大正方形
时间: 2024-05-04 10:20:35 浏览: 31
可以使用动态规划来解决这个问题。假设我们有一个由 0 和 1 组成的矩阵,定义一个新的矩阵 dp,其中 dp[i][j] 表示以点 (i, j) 为右下角的最大正方形的边长。那么,如果当前点 (i, j) 是 1,则有:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
也就是说,当前点的最大正方形边长等于其上、左、左上三个点的最小正方形边长加上 1。这是因为当前点可以和这三个点组成一个更大的正方形。如果当前点是 0,则 dp[i][j] = 0。
接下来,我们需要遍历整个矩阵,计算出 dp 数组的值。最后,我们找到 dp 数组中的最大值,即为矩阵中由 1 组成的最大正方形的边长。
以下是 Python 代码实现:
```python
def maximalSquare(matrix: List[List[str]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if matrix[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_len = max(max_len, dp[i][j])
return max_len * max_len
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)