铁道部建设管理司网站,wordpress 友情链接插件,做低价的跨境电商网站,建网站 服务器需要安装 tomcat摘要
1139. 最大的以 1 为边界的正方形
一、以1为边界的最大正方形
1.1 动态规划
第530题需要正方形所有网格中的数字都是1#xff0c;只要搞懂动态规划的原理#xff0c;代码就非常简洁。而这题只要正方形4条边的网格都是1即可#xff0c;中间是什么数字不用管。
这题…摘要
1139. 最大的以 1 为边界的正方形
一、以1为边界的最大正方形
1.1 动态规划
第530题需要正方形所有网格中的数字都是1只要搞懂动态规划的原理代码就非常简洁。而这题只要正方形4条边的网格都是1即可中间是什么数字不用管。
这题解题思路是这样的
第一步先计算每个网格中横向和竖向连续1的个数。第二步遍历二维网格以每一个格子为正方形的右下角分别找出上边和左边连续1的个数取最小值作为正方形的边长然后判断正方形的左边和上边长度是否都大于等于正方形边长如果都大于等于正方形边长就更新正方形的最大边长否则缩小正方形的边长继续判断……。代码比较简单我们定义一个三维数组其中
dp[i][j][0]: (i,j)横向连续1的个数dp[i][j][1]: (i,j)竖向连续1的个数
第一步 我们计算的时候如果当前位置是0就跳过只有是1的时候才计算分别统计左边和上边也就是横向和竖向连续1的个数。代码比较简单我们来看下这里为了减少一些边界条件的判断把dp的宽和高都增加了1。
int m grid.length;
int n grid[0].length;
//dp[i][j][0]: (i,j)横向连续1的个数
//dp[i][j][1]: (i,j)竖向连续1的个数
int[][][] dp new int[m 1][n1][2];
for (int i 1; i m; i) {for (int j 1; j n; j) {//如果当前位置是0就跳过if (grid[i - 1][j - 1] 0)continue;//如果是1我们就计算横向和竖向连续1的个数dp[i][j][0] dp[i][j - 1][0] 1;dp[i][j][1] dp[i - 1][j][1] 1;}
}
第二步找出正方形的最大边长
我们会以网格中的每一个位置为正方形的右下角来找出正方形的边长。如下图所示我们以橙色的位置1为正方形的右下角分别沿着左边和上边找出他们连续1的个数最小的作为正方形的边长。因为左边和上边连续1的个数我们在第一步的时候已经计算过分别是dp[i][j][0]和dp[i][j][1]也就是正方形的边长我们暂时可以认为是 其实大家已经看到了这个边长就是正方形下边和右边的长度但是正方形的上边和左边我们还没确定我们继续确定正方形左边和上边的长度。会有两种情况
一种如下图所示就是正方形左边和上边的长度都大于curSide我们可以认为以坐标(i,j)为右下角的正方形的最大长度就是curSide。另一种如下图所示正方形上边的长度是1小于curSide。 这种情况下是构不成正方形的所以我们要缩小curSide的值然后再继续判断
public int largest1BorderedSquare(int[][] grid) {int m grid.length;int n grid[0].length;//dp[i][j][0]: (i,j)横向连续1的个数//dp[i][j][1]: (i,j)竖向连续1的个数int[][][] dp new int[m 1][n 1][2];for (int i 1; i m; i) {for (int j 1; j n; j) {//如果当前位置是0就跳过if (grid[i - 1][j - 1] 0)continue;//如果是1我们就计算横向和竖向连续1的个数dp[i][j][0] dp[i][j - 1][0] 1;dp[i][j][1] dp[i - 1][j][1] 1;}}int maxSide 0;//记录正方形的最大长度for (int i 1; i m; i) {for (int j 1; j n; j) {//沿着当前坐标往上和往左找出最短的距离暂时看做是正方形的边长(正方形的具体边长//还要看上边和左边的长度所以这里要判断一下)int curSide Math.min(dp[i][j][0], dp[i][j][1]);//如果边长小于maxSide即使找到了也不可能再比maxSide大所以我们没必要再找直接跳过if (curSide maxSide)continue;//curSide可以认为是正方形下边和右边的长度我们还需要根据正方形上边和左边的长度//来确认是否满足正方形的条件for (; curSide maxSide; curSide--) {//判断正方形的左边和上边的长度是否大于curSide如果不大于我们就缩小正方形//的长度curSide然后继续判断if (dp[i][j - curSide 1][1] curSide dp[i - curSide 1][j][0] curSide) {maxSide curSide;//更短的就没必要考虑了这里直接中断break;}}}}//返回正方形的边长return maxSide * maxSide;
}
复杂度分析
时间复杂度O(m×n×min(m,n))其中 m 表示矩阵的行数n 表示矩阵的列数。空间复杂度O(m×n)其中 m 表示矩阵的行数n 表示矩阵的列数。需要保存矩阵中每个位置的最长连续1的数目需要的空间为 O(m×n)。
二、只是包含1的最大正方形
221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内找到只包含 1 的最大正方形并返回其面积。 2.1 暴力求解
由于正方形的面积等于边长的平方因此要找到最大正方形的面积首先需要找到最大正方形的边长然后计算最大边长的平方即可。
暴力法是最简单直观的做法具体做法如下
遍历矩阵中的每个元素每次遇到 1则将该元素作为正方形的左上角确定正方形的左上角后根据左上角所在的行和列计算可能的最大正方形的边长正方形的范围不能超出矩阵的行数和列数在该边长范围内寻找只包含 1 的最大正方形每次在下方新增一行以及在右方新增一列判断新增的行和列是否满足所有元素都是 1。package matrix;/*** Classname 最大的正方形221* Description TODO* Date 2023/2/17 7:50* Created by xjl*/
public class 最大的正方形221 {public int maximalSquare(char[][] matrix) {int maxSide0;if (matrixnull||matrix.length0||matrix[0].length0){return maxSide;}int rowsmatrix.length,columsmatrix[0].length;for (int i0;irows;i){for (int j0;jcolums;j){if (matrix[i][j]1){// 遇到一个 1 作为正方形的左上角maxSideMath.max(maxSide,1);// 计算可能的最大正方形边长 剩下的矩阵中的最大的正方形int currentMaxSideMath.min(rows-i,colums-j);for (int k 1; k currentMaxSide; k) {// 判断新增的一行一列是否均为 1boolean flag true;// 判断是下一行和下一列是否为0 判断所有的对角线的元素 如果有存在的那就判断其他的四条边if (matrix[i k][j k] 0) {break;}for (int m 0; m k; m) {if (matrix[i k][j m] 0 || matrix[i m][j k] 0) {flag false;break;}}if (flag) {maxSide Math.max(maxSide, k 1);} else {break;}}}}}int maxSquare maxSide * maxSide;return maxSquare;}
}2.2 动态规划求解
可以使用动态规划降低时间复杂度。我们用 dp(i,j) 表示以 (i,j) 为右下角且只包含1的正方形的边长最大值。如果我们能计算出所有dp(i,j) 的值那么其中的最大值即为矩阵中只包含1的正方形的边长最大值其平方即为最大正方形的面积。
那么如何计算 dpdp 中的每个元素值呢对于每个位置 (i,j)(i,j)检查在矩阵中该位置的值
如果该位置的值是 0则 dp(i,j)0因为当前位置不可能在由 1 组成的正方形中如果该位置的值是 1则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的dp值决定。具体而言当前位置的元素值等于三个相邻位置的元素中的最小值加1状态转移方程如下此外还需要考虑边界条件。如果 i 和 j 中至少有一个为0则以位置 (i,j)为右下角的最大正方形的边长只能是 1因此 dp(i,j)1。 class Solution {public int maximalSquare(char[][] matrix) {int maxSide 0;if (matrix null || matrix.length 0 || matrix[0].length 0) {return maxSide;}int rows matrix.length, columns matrix[0].length;int[][] dp new int[rows][columns];for (int i 0; i rows; i) {for (int j 0; j columns; j) {if (matrix[i][j] 1) {if (i 0 || j 0) {dp[i][j] 1;} else {dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1;}maxSide Math.max(maxSide, dp[i][j]);}}}int maxSquare maxSide * maxSide;return maxSquare;}
}
复杂度分析
时间复杂度O(mn)其m 和 n是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算dp的值。空间复杂度O(mn)其中 m和n是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵 dp。由于状态转移方程中的 dp(i,j)由其上方、左方和左上方的三个相邻位置的 dp值决定因此可以使用两个一维数组进行状态转移空间复杂度优化至O(n)。
博文参考
《leetcode》
