python 练习题-取小正方形(LeetCode 221)

题目:

给定一个矩阵,该矩阵只包含0和1,输出该矩阵中最大正方形区域的面积
如:
00011110
00001111
11101111

最大是 3X3 的正方形,输出为 9

 

解题:

1.参考相关博客(链接见下文)
先新建一个全为0,行数和列相等的列表 dp,设置一个最大值 maxSquare
1)第一行和第一列,如果等于1,则dp对应的值为1
2)除此之外,如果该值等于1,取该值左边、上边、左上中的最小值+1 
该值为dp对应的值
3)取 maxSquare 和该值的最大值,赋值给 maxSquare
4)返回 maxSquare * maxSquare

以上是取1中的最大正方形,取0中的最大正方形也类似,最后取 1和0中最大值中的最大值即可

 

代码:

 1 from typing import List
 2 """
 3 输出矩阵最大面积
 4 """
 5 class Solution:
 6     def maximalSquare(self, matrix: List[List[str]]) -> int:
 7         #长度为0,直接返回0
 8         if len(matrix) == 0 or len(matrix[0]) == 0:
 9             return 0
10 
11         maxSide1 = 0
12         maxSide0 = 0
13         rows, columns = len(matrix), len(matrix[0])
14 
15         #新增二个全为0的数组
16         dp1 = [[0] * columns for _ in range(rows)]
17         dp0 = [[0] * columns for _ in range(rows)]
18 
19         for i in range(rows):
20             for j in range(columns):
21                 #取1中的最大正方形
22                 if matrix[i][j] == '1':
23                     # 第一行和第一列为1时,新数组值为1
24                     if i == 0 or j == 0:
25                         dp1[i][j] = 1
26                     #取改值左边、上边、左上中的最小值+1
27                     else:
28                         dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1], dp1[i - 1][j - 1]) + 1
29                     maxSide1 = max(maxSide1, dp1[i][j])
30 
31                 # 取0中的最大正方形
32                 if matrix[i][j] == '0':
33                     # 第一行和第一列为0时,新数组值为1
34                     if i == 0 or j == 0:
35                         dp0[i][j] = 1
36                     # 取改值左边、上边、左上中的最小值+1
37                     else:
38                         dp0[i][j] = min(dp0[i - 1][j], dp0[i][j - 1], dp0[i - 1][j - 1]) + 1
39                     maxSide0 = max(maxSide0, dp0[i][j])
40 
41         #取0,1中的最大值
42         maxSide = max(maxSide1,maxSide0)
43         maxSquare = maxSide * maxSide
44         return maxSquare
45 
46 s = Solution()
47 print(s.maximalSquare(['1110','1110','1110']))

 

 

 

 

参考博客:https://blog.csdn.net/AI414010/article/details/108985709

题目来源:

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximal-square/

上一篇:[LeetCode] #121 买卖股票的最佳时机


下一篇:Codeforces Round #715 (Div. 2) (A~C 补题记录)