建购物网站,页面设计在哪里找,零基础能做网络推广吗,上海到北京高铁票价多少文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述
在一个由 0 和 1 组成的二维矩阵内#xff0c;找到只包含 1 的最大正方形#xff0c;并返回其面积。
示例 1 输入#xff1a;matrix [[1,0,1,00 和 1 组成的二维矩阵内找到只包含 1 的最大正方形并返回其面积。
示例 1 输入matrix [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]
输出4示例 2 输入matrix [[0,1],[1,0]]
输出1示例 3
输入matrix [[0]]
输出0提示 m matrix.length n matrix[i].length 1 m, n 300 matrix[i][j] 为 0 或 1
二、代码
代码如下
import numpy as np
class Solution:def maximalSquare(self, matrix: List[List[str]]) - int:row len(matrix)col len(matrix[0])result 0for i in range(row):for j in range(col):if matrix[i][j] 0:continueelif i ! 0 and j ! 0:if matrix[i][j-1] and matrix[i-1][j] and matrix[i-1][j-1] and int(matrix[i][j-1]) 0 and int(matrix[i-1][j]) 0 and int(matrix[i-1][j-1]) 0:matrix[i][j] str(min(int(matrix[i][j-1]),int(matrix[i-1][j]),int(matrix[i-1][j-1])) 1)if int(matrix[i][j]) result:result int(matrix[i][j])print(result**2)return result**2 三、解题思路
本题考验的对于数组的遍历判断操作需要我们找出由1构成的最大的正方形面积。本题解采用动态规划的方法由于当前所判断的结果对于之后的判断也有用上所以使用动态规划的方法较好如果采用暴力遍历的方式的话则会导致运算超时。 具体思路如下 以当前的坐标[i][j]为例需要判断的是当前坐标的左上左上这3个点对应的坐标为[i][j-1][i-1][j][i-1][j-1]如果坐标存在的话判断这3个点是否都是大于0的如果是并且当前坐标[i][j]不为0则以上这4个点可以构成一个更大的正方形如果不是或者当前坐标[i][j]等于0则无法构成更大的正方形。 如果能够构成更大的正方形则当前坐标[i][j]则需要进行更新更新方式为选取其左、上、左上3个坐标中的最小值 1。 最后在每次进行更新操作时记录下当前更新后的最大值返回其平方数即可。
