首页 > 试题广场 >

最大正方形

[编程题]最大正方形
  • 热度指数：24734 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个由 '0' 和 '1' 组成的2维矩阵，返回该矩阵中最大的由 '1' 组成的正方形的面积。输入的矩阵是字符形式而非数字形式。

数据范围：矩阵的长宽满足 ,矩阵中的元素属于 {'1','0'}
进阶：空间复杂度 ， 时间复杂度
示例1

输入

[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]

输出

4
示例2

输入

[[1,0,0],[0,0,0],[0,0,0]]

输出

1
算法知识视频讲解
开通博客
头像 数据结构和算法
发表于 2021-07-02 11:41:04
精华题解 动态规划解决 这题让求的是由1围成的最大正方形，最容易想到的一种方式就是暴力求解。解决方式就是如果某个位置是1，就以他为正方形左上角，然后沿着右边和下边找最大的正方形，并且还要保证围成的正方形中所有的数字都是1。 这种虽然容易想到但代码不太好写，并且时间复杂度也比较高。下面我们来看另一种实现方式，使 展开全文
去ta的博客 赞 (33) 回复(7) 收起
头像 ACJavaBear
发表于 2020-09-16 20:06:38
一、须知 题解简略，仅供参考。 答主水平有限，如有错误请在评论区提醒一下，有更好的解法或改进代码也欢迎来一起探讨。十分感谢！ 二、题解 根据DP解题的三步骤 1.确定dp[][]数组的含义 此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。 2.状态转移方程 dp[i][j 展开全文
去ta的博客 赞 (8) 回复(3) 收起
头像 Maokt
发表于 2021-07-24 10:40:08
算法思想一：暴力法 解题思路： 由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。 暴力法是最简单直观的做法，具体做法如下： 1、遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角； 2、确定正方形的左上角 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Stackingrule
发表于 2020-08-13 16:17:58
NC108-最大正方形-暴力法 这种方法的机理就是就是把数组中每一个点都当成正方形的左顶点来向右下方扫描，来寻找最大正方形。具体的扫描方法是，确定了左顶点后，再往下扫的时候，正方形的竖边长度就确定了，只需要找到横边即可，这时候我们使用直方图的原理，从其累加值能反映出上面的值是否全为1。 class 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 B612_2024
发表于 2021-12-03 18:39:57
public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector< 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客289281343号
发表于 2020-10-28 21:35:16
解题思路：根据提示，采用动态规划的方法求解。观察规律，除了单个元素的正方形，其余常规的正方形判断如下，1 11 1这是一个正方形，是因为arr[i-1][j-1]，arr[i-1][j]，arr[i][j-1]，arr[i][j]的元素相同增加问题规模，继续观察，1 1 11 1 11 1 1这是一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 开车的阿Q
发表于 2021-08-17 00:22:32
描述 这是一篇面对初级coder的题解。 知识点：动态规划 二维vector使用 难度：二星 题解 给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积 分析： 与NC109相比，由于寻找的正方形较为规整 所以可以动态规划 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 include<cc>
发表于 2021-11-01 18:25:52
class Solution { public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vec 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 神奇.瀚
发表于 2021-02-04 23:59:31
视频连接：https://www.bilibili.com/video/BV1po4y1d7C9/ class Solution: def solve(self , matrix ): if not matrix: return 0 rows = len(ma 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 shredderzwj
发表于 2021-11-08 16:46:35
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 最大正方形 # @param matrix char字符型二维数组 # @return int整型 # class Solution: def solve(self , matrix: List[Li 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 业精于勤110
发表于 2022-05-19 09:19:23
【二维dp】 dp[i][j]表示以(i,j)为右下角的最大正方形的边长 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 最大正方形 # @param matrix char字符型二维数组 # @return int整型 # class Solution: 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划
上传者：牛客332641号
难度：
57条回答 4986浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大正方形

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号