天津知名网站建设公司,呼市网站制作招聘,网站赞赏,西宁做网站需要多少钱最大的以 1 为边界的正方形
难度#xff1a;中等
给你一个由若干 0 和 1 组成的二维网格 grid#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格#xff0c;并返回该子网格中的元素数量。如果不存在#xff0c;则返回 0。
示例 1#xff1a;
输入#xff1a…最大的以 1 为边界的正方形
难度中等
给你一个由若干 0 和 1 组成的二维网格 grid请你找出边界全部由 1 组成的最大 正方形 子网格并返回该子网格中的元素数量。如果不存在则返回 0。
示例 1
输入grid [[1,1,1],[1,0,1],[1,1,1]]
输出9示例 2
输入grid [[1,1,0,0]]
输出1前缀和
思路
数据量较小也可以用二维前缀和写用前缀和节省边长的计算时间遍历正方形边长求出区域和然后减去中间那块区域是否等于两边都为111的和假如正方形边长为333那么边长都为111的和为: 32−(3−2)283^2-(3-2)^2832−(3−2)28
复杂度分析
时间复杂度 O(mn)O(mn)O(mn)其中 mmm 和 nnn 分别为 grid\textit{grid}grid 的行数和列数不一定是mnmnmn大佬可是帮我分析一下是多少。空间复杂度 O(mn)O(mn)O(mn)。
class Solution:def largest1BorderedSquare(self, grid) - int:# 构建前缀和行列各构建一个数组row, col len(grid), len(grid[0])prev_row [[0] * (col 1) for _ in range(row)]prev_col [[0] * (row 1) for _ in range(col)]for i in range(row):for j in range(col):prev_row[i][j1] prev_row[i][j] grid[i][j]prev_col[j][i1] prev_col[j][i] grid[i][j]# 遍历所有元素res 0 for i in range(row):for j in range(col):# 如果该节点为1则可能是正方形的左顶点if grid[i][j] 1:# 令长度等于当前遍历过的最大长度length res# 慢慢增加边长看是否能成立while length i row and length j col:# 如果长度不合适那无论怎么增加长度都不可能是正方形直接退出if prev_row[i][j length] - prev_row[i][j] ! length:break# 计算4条边的长度fh prev_row[i][j length] - prev_row[i][j]fl prev_col[j][i length] - prev_col[j][i]lh prev_row[i length - 1][j length] - prev_row[i length - 1][j]ll prev_col[j length - 1][i length] - prev_col[j length - 1][i]# 判断边上的点是否等于边长为length的值如果相等那他就是一个正方形if length ** 2 - max(0, length - 2)**2 fh fl lh ll - 4:res max(res, length)length 1# 因为边长为1的时候他的边长不是 四条边分别的元素个数 - 4而且只要有原始是1# 就说明是边长为1的正方向所以每次出来的时候让他和1取最大的边长为结果if res 1:res 1return res ** 2来源力扣LeetCode 链接https://leetcode.cn/problems/largest-1-bordered-square
