首页 / PYTHON / python 练习题-取小正方形（LeetCode 221）

python 练习题-取小正方形（LeetCode 221）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python 练习题-取小正方形（LeetCode 221），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1630字，纯文字阅读大概需要3分钟。

内容图文

题目：

            给定一个矩阵，该矩阵只包含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""" 5class Solution:
 6def maximalSquare(self, matrix: List[List[str]]) -> int:
 7#长度为0，直接返回0 8if len(matrix) == 0 or len(matrix[0]) == 0:
 9return 0
1011         maxSide1 = 0
12         maxSide0 = 0
13         rows, columns = len(matrix), len(matrix[0])
1415#新增二个全为0的数组16         dp1 = [[0] * columns for _ in range(rows)]
17         dp0 = [[0] * columns for _ in range(rows)]
1819for i in range(rows):
20for j in range(columns):
21#取1中的最大正方形22if matrix[i][j] == ‘1‘:
23# 第一行和第一列为1时，新数组值为124if i == 0 or j == 0:
25                         dp1[i][j] = 1
26#取改值左边、上边、左上中的最小值+127else:
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])
3031# 取0中的最大正方形32if matrix[i][j] == ‘0‘:
33# 第一行和第一列为0时，新数组值为134if i == 0 or j == 0:
35                         dp0[i][j] = 1
36# 取改值左边、上边、左上中的最小值+137else:
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])
4041#取0,1中的最大值42         maxSide = max(maxSide1,maxSide0)
43         maxSquare = maxSide * maxSide
44return maxSquare
4546 s = Solution()
47print(s.maximalSquare([‘1110‘,‘1110‘,‘1110‘]))

 

 

 

 

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

题目来源：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square/

原文：https://www.cnblogs.com/whycai/p/14385587.html

内容总结

以上是互联网集市为您收集整理的python 练习题-取小正方形（LeetCode 221）全部内容，希望文章能够帮你解决python 练习题-取小正方形（LeetCode 221）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1112550.html

来源：【匿名】