【LeetCode】221.最大正方形

0.总结

• 注意 copy 的使用。

---

1.题目

2.思想

• (1)dp[i][j] 表示以 matrix[i][j] 为结尾得到的最大正方形边长
• (2)得到递推式： min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

3.代码

import copy 
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        dp = copy.deepcopy(matrix)
        m,n = len(matrix),len(matrix[0])
        
        # 修改预处理的部分
        for i in range(m):
            for j in range(n):
                dp[i][j] = int(dp[i][j])
        dp.append([0]*len(matrix[0])) # 添加新的一行

        for i in range(m+1):
            dp[i].append(0)
        # print(dp)
        # print(matrix)

        # 找出最大边长
        span = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    span = max(span,dp[i][j])    
        return span**2
        # return dp[m-1][n-1]

上面这个代码是使用了额外数组空间的。可以再进一步整合只使用 matrix 也是可以的。

''' 思想 (1)dp[i][j] 表示以 matrix[i][j] 为结尾得到的最大正方形边长 (2)得到递推式： dp[i][j] = dp[] '''
import copy 
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:        
        m,n = len(matrix),len(matrix[0])        
        # 修改预处理的部分
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
        matrix.append([0]*len(matrix[0])) # 添加新的一行

        for i in range(m+1):
            matrix[i].append(0)
        
        # 找出最大边长
        span = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])+1
                    span = max(span,matrix[i][j])
        return span**2
        # return dp[m-1][n-1]