一、题目 1、算法题目 “在0和1组成的矩阵中找到只包含1的最大正方形,返回其面积。” 题目链接: 来源:力扣(LeetCode) 链接: 221....最大正方形 - 力扣(LeetCode) 2、题目描述 在一个由 '0' 和 '1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。..."0","1","0"]] 输出:4 示例 2: 输入: matrix = [["0","1"],["1","0"]] 输出: 1 二、解题 1、思路分析 题意要在0和1组成的二维矩阵中找到只包含1的最大正方形...由于正方形的面积等于边长的平方,因此要找到最大的正方形的面积,就需要找到最大正方形的边长,然后计算最大边长的平方即可。 具体的,就是遍历矩阵中的每个元素,遇到1,则将钙元素作为正方形的左上角。...确定左上角后,根据左上角的行和列计算可能的正方形的边长,在行数和列数的范围内找出只包含1的最大正方形。 每次右或下新增一行,判断新增的行和列是否满足所有元素都是1。
4.解题思路 4.1 暴力法 4.1.1 思路 暴力求解思想非常朴素: 遍历矩阵,遇到 1 则作为最大正方形的左上角; 根据左上角所在的行和列计算可能的最大正方形; 在可能的最大正方形内,每次循环在下方一行和右方一列验证是否所有元素都是...我们用 dp(i, j) 表示以 (i, j) 为右下角,且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值,那么其中的最大值的平方即为题解。...遍历完矩阵便可求出全为 1 的最大正方形面积。 空间复杂度 O(mn),其中 m 和 n 是矩阵的行数和列数。因为要记录每一个位置的最大正方形边长,所以需要 mn 个额外空间。...5.1 C++ #include // maximalSquare 最大正方形面积。...最大正方形 - leetcode
思路: 我们用 dp(i,j) 表示以 (i, j)(i,j) 为右下角,且只包含 1 的正方形的边长最大值。...如果我们能计算出所有dp(i,j) 的值,那么其中的最大值即为矩阵中只包含 11 的正方形的边长最大值,其平方即为最大正方形的面积。 那么如何计算 \textit{dp}dp 中的每个元素值呢?...[j],dp[i][j-1],dp[i-1][j-1]) public int maximalSquare(char[][] matrix) { //max存储最大边长
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
题目描述 在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。...输出格式: 一个整数,最大正方形的边长 输入输出样例 输入样例#1: 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 输出样例#1: 2 1 #include<iostream
原题 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。...假设我们用一个二维数组dp,记录每一个位置所能构成的最大正方形的边长(从左上角开始算)。...位置(i, j)是 1,则其可能构成的正方形的边长是Min(dp(i - 1, j - 1), dp(i - 1, j), dp(i, j - 1)) + 1。...看到这个,相信你也会理解了,每一个位置所能构成的最大边长的条件,其实是要求包围着它的左上角三个位置都是 1 才可以。 一直递推回到最初点,也就意味着,第一行和第一列需要单独判断。...其实我们发现,当一个位置用过之后,这个位置本身的数字已经不再重要,关键是该位置所能构成的最大正方形的边长,也就是我们记录的中间结果。因此可以直接更新原数组上的数字。
# LeetCode-221-最大正方形 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。...; 确定正方形的左上角后,根据左上角所在的行和列计算可能的最大正方形的边长(正方形的范围不能超出矩阵的行数和列数),在该边长范围内寻找只包含 1 的最大正方形; 每次在下方新增一行以及在右方新增一列,判断新增的行和列是否满足所有元素都是...方法2、动态规划: 状态dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长 则当i==0或者j==0,最大正方形边长始终为1,则dp[i][j]=1 右下角的正方形的最大边长,最多比它的上方...maxSide = Math.max(maxSide, 1); // 计算可能的最大正方形边长...int currentMaxSide = Math.min(rows - i, columns - j); // 遍历可能的最大正方形内的每个元素
思路 使用动态规划来求解,算法时间复杂度O(n^2)。 dp[i][j] : 以(i, j)为右下角的面积最大的正方形的边长。 初始条件:最上面一行,最左边一列,可以直接得到dp值。
题目 在一个二维01矩阵中找到全为1的最大正方形 样例 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 返回 4 分析 动态规划 dp[i][j]:最大正方形的边长...if(n > 0) m = matrix[0].length; else return ans; //dp[i][j] 最大正方形的边长...dp[0][i] = matrix[0][i]; ans = 1; } //状态转移方程,用ans存储最大边长
题目信息 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: ?...最大矩形(DP,难) ? ?...maxEdgeLen = 0; int r = matrix.size(), c = matrix[0].size(); int dp[r][c];//以右下角为结束的最大正方形边长...又发现以(i,j)为右下角的最大正方形边长 dp[i][j] 就是 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])(i,j 位置左上角3个点的最大边长中的最小者)...incr, maxlen = 0; int r = matrix.size(), c = matrix[0].size(); int dp[r][c];//以右下角为结束的最大正方形边长
学好算法没有捷径,最好的捷径就是多刷题,并且跳出舒适区,每道题都要寻找最优解,也不能老是做那些你自己比较擅长的题,不定期更新 Leetcode 的题,每道题都会给出多种解法以及最优解 题目描述 在一个由...0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。...搜索的过程中,用一个变量来记录最大正方形的面积。接着用(0,1)作为左上角,不断着向右下角搜索 ? 当然,(0,1)这个位置本身就是 0 ,所以是没有搜索的必要的,我这里只是做个演示。...1、首先我们定义 dp[i][j] 含义为正方形以 dp[i][j] 作为右下角时的最大边长值。...时间复杂度:O(n*m) 空间复杂度:O(n) 额外话 动态规划是一个比较难的算法思想,特别是对于初学者,遇到动态规划的题基本凉,我刚开始也被搞过,后来能看懂关于动态规划的答案,但是自己写不出,一气之下做了几十道动态规划的题
1 题目描述 0 和 1 组成一个字符型二维矩阵,在其中找到只包含 1 的最大正方形,并返回其面积。...第一步,找到中间状态:此处中间状态st[i][j]表示以矩阵中(i,j)元素作为正方形右下角顶点,可以得到最大正方形边长。
package *; /** * @program: data-structure * @description: 正方形 * @author: ChenWenLong * @create:...printSolidSquare(10); printHollowSquare(10); } /** * 功能描述: * 〈答应实心的正方形...,rowNum为你想要打印正方形的行数〉 * * @params : [rownum] * @return : void * @author : cwl...else { System.out.println("数字应大于1"); } } /** * 功能描述: * 〈打印空心正方形
---- 【题目】 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。...示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4 【思路】 这道题我想着用【数组中最大矩形】的思路来做,想复杂了…… 我们首先遍历每一行,得到高度...用一个变量max_size存储当前最大边长,当每一行的高度数组中,连续大于max_size的元素个数大于max_size,那么max_size++。 最后返回max_size * max_size。
最大正方形 链接:https://leetcode-cn.com/problems/maximal-square 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
题目描述 小明有一些矩形的材料,他要从这些矩形材料中切割出一些正方形。...当他面对一块矩形材料时,他总是从中间切割一刀,切出一块最大的正方形,剩下一块矩形,然后再切割剩下的矩形材料,直到全部切为正方形为 止。...形 依次切出3x3、2x2 1x1 1x1共4个正方形 例如,对于一块两边分别为5和3的材料(记为5x3),小明会 切 最终会切出多少个正方形?...int count = 0; //取最小边和最大边 int maxSide = max(longSide,width); int minSide...int count = 0; //取最小边和最大边 int maxSide = max(longSide, width);
最大正方形问题 题目:https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_A 现有HxW个边长为1的瓷砖拼在一起,其中一部分瓷砖有污迹...,求仅由干净瓷砖构成的最大正方形的面积。...0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 Sample Output 4 这题可以通过dp来解决,用数组dp[i][j]来表示以顶点(i,j)向左上角扩展,得到的最大正方形的边长...最大长方形问题和上面的一题类似,只是要求最大的干净的长方形的面积。...如果栈为空 将rect压入栈 如果栈顶长方形高度<=rect的高 将rect压入栈 如果栈顶长方形的高大于rect的高 只要栈不为空,且栈顶长方形的高>=rect的高,就从栈中取出长方形,同时计算其面积并更新最大值
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。...matrix.length n == matrix[i].length 1 <= m, n <= 300 matrix[i][j] 为 ‘0’ 或 ‘1’ 题解 动态规划,f[i][j]代表以i,j为下表最大能构成的正方向
如果存在 k同时满足 k <= li 和 k <= wi,就可以将第 i个矩形切成边长为 k的正方形。例如,矩形 [4,6]可以切成边长最大为 4的正方形。...设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。 返回可以切出边长为 maxLen 的正方形的矩形 数目 。...示例 示例 1: 输入:rectangles = [[5,8],[3,9],[5,12],[16,5]] 输出:3 解释:能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。...最大正方形的边长为 5 ,可以由 3 个矩形切分得到。...我们可以用一个对象去记录最小值出现的次数,然后求其最大值的次数。
领取专属 10元无门槛券
手把手带您无忧上云