同一矩阵上的最大平方dp

问题描述 投票:0回答:1

问题最大平方在 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
algorithm dynamic-programming python-3.7
1个回答
1
投票

我猜你没有处理好角的情况。对我来说,这段代码只要稍加修改就能运行得很好.另外,这样运行会有点慢。

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的填充,它使公式工作而不检查边界。

© www.soinside.com 2019 - 2024. All rights reserved.