最大正方形(Python)

最大正方形

http://www.nowcoder.com/questionTerminal/0058c4092cec44c2975e38223f10470e

动态规划

主要思想

创建一个二维 dp 数组,接着遍历矩阵,然后在 dp 里面存储当前遍历到的最大的正方形的边长,最后取出 dp 的最大值,平方即面积。

状态转移方程

讨论区第一个那个图 其实已经很明了了,但我这里还是提一嘴。
0 自然没什么问题;至于 min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1,其中的 1 指的是当前块,min 大家想一下就知道了,类似于 短板效应,最大的 囊括当前块 的正方形当然取决于最短的那条边。

ps: 几个小技巧

  • 巧用 map 取二维数组最值
  • 一般而言 * 快于 power 快于 **
#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix ):
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0':
                    dp[i][j] = 0
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        res = max(map(max, dp))
        return res * res
全部评论
eles里边求res和dp[i][j]重的较大值,也可以直接输出,不需要再求做大值了
点赞 回复 分享
发布于 2021-05-16 17:18

相关推荐

07-01 19:00
门头沟学院 Java
点赞 评论 收藏
分享
05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
简历中的项目经历要怎么写
点赞 评论 收藏
分享
06-26 17:24
已编辑
宁波大学 Java
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务