问题最大平方在 https:/leetcode.comproblemsmaximal-squaredescription。 但我没有创建一个新的矩阵,而是在原来的矩阵上进行了修改,但这种方法在测试用例64中失败了,请检查我的以下代码,并帮助我找出缺失点。
def maximalSquare(self, matrix: List[List[str]]) -> int:
for x in range(1,len(matrix)):
for y in range(1,len(matrix[x])):
if matrix[x][y] == '1':
matrix[x][y] = str(int(min( matrix[x-1][y], matrix[x][y-1], matrix[x-1][y-1]))+1)
return int(max([max(x) for x in matrix])) ** 2 if matrix else 0
我猜你没有处理好角的情况。对我来说,这段代码只要稍加修改就能运行得很好.另外,这样运行会有点慢。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix: return 0
m, n, res = len(matrix), len(matrix[0]), 0
for i in range(m):
for j in range(n):
if (i == 0 or j == 0) and (matrix[i][j] == '1'):
res = max(res, 1)
elif int(matrix[i][j]) == 1:
matrix[i][j] = min(int(matrix[i-1][j]), int(matrix[i][j-1]), int(matrix[i-1][j-1])) + 1
res = max(res, matrix[i][j])
return res ** 2
当迭代第一行或第一列时,dp(i, j)的公式正在检查是否有超出边界的值。通过将整个dp向右和底部移动1,并在第1行和第1列添加0的填充,它使公式工作而不检查边界。