淘宝客单页网站程序,手机app开发工具下载,鑫路网站建设,深圳 网站建设培训学校来源#xff1a;LeetCode第1139题
难度:中等
描述#xff1a;给你一个由若干0和1组成的二维网格grid#xff0c;请你找出边界全部由1组成的最大正方形子网格#xff0c;并返回该子网格中的元素个数#xff0c;若不存在#xff0c;则返回0#xff1b;
思路#xff1a…来源LeetCode第1139题
难度:中等
描述给你一个由若干0和1组成的二维网格grid请你找出边界全部由1组成的最大正方形子网格并返回该子网格中的元素个数若不存在则返回0
思路申请三个空间第一个二维空间dp1[i][j]这个空间表示第i行第j列在[i][j]这个位置前面(左边)连续1的个数包括自己。第二个二维空间dp2[i][j],这个空间表示第i行第j列在[i][j]这个位置上面联系1的个数包括自己。第三个二维空间dp3[i][j]表示以[i][j]为右下角的最大正方形边长。
//首先定义一个函数输入值时grid的二维数组返回值是最大正方形元素的个数
public int maxSquare(int [][]grid)
{
//求grid矩阵的行数
int rowgrid.length;
//求grid矩阵的列数默认为长方形
int columngrid[0].length;
//生成3个动态数组
//第一个动态数组dp1[i][j]表示[i][j]位置处左边连续1的个数
int [][]dp1new int[row][column];
//第二个动态数组dp2[i][j]表示[i][j]位置处上方连续1的个数
int [][]dp2new int[row][column];
//第三个动态数组dp3[i][j]表示以[i][j]为右下角的最大正方形面积围成的最大正方形边长*边长
int [][]dp3new int[row][column];
//首先进行dp1[i][j]数组第一列的初始化若第一个元素为1则dp1[i][0]1,否则dp1[i][0]0;
for(int i0;igrid.length;i)
{
if(grid[i][0]1)
{
dp1[i][0]1;
}else
{
dp1[i][0]0;
}
}
//其次进行dp2[i][j]数组第一行的初始化若第一个元素为1则dp2[0][i]1,否则dp2[0][i]0;
for(int i0;igrid[0].length;i)
{
if(grid[0][i]1)
{
dp2[0][i]1;
}else
{
dp2[0][i]0;
}
}
//进行dp1[i][j]动态数组的递推公式如果grid[i][j]1,则dp1[i][j]dp1[i][j-1]1否则为0
for(int i0;igrid.length;i)
{
for(int j1;jgrid[i].length;j)
{
if(grid[i][j]1)
{
dp1[i][j]dp1[i][j-1]1;
}else
{
dp1[i][j]0;
}
}
}
//进行dp2[i][j]动态数组的递推公式如果grid[i][j]1,dp2[i][j]dp[i-1][j]1;否则为0
for(int i1;igrid.length;i)
{
for(int j0;jgrid[i].length;j)
{
if(grid[i][j]1)
{
dp2[i][j]dp[i-1][j]1;
}else
{
dp2[i][j]0;
}
}
}
//进行dp3[i][j]动态数组第一列的初始化若对应位置为1则dp3[i][0]1;
for(int i0;igrid.length;i)
{
if(grid[i][0]1)
{
dp3[i][0]1;
}else
{
dp3[i][0]0;
}
}
//进行dp3[i][j]动态数组第一行的初始化若对应位置为1则dp3[0][i]1;
for(int i1;igrid[0].length;i)
{
if(grid[0][i]1)
{
dp3[0][i]1;
}else
{
dp3[0][i]0;
}
}
//定义变量maxsize表示从[i][j]位置上下寻找到的最大正方形边长
int maxside0;
//记录最大的正方形边长并最后返回
int maxsquqre0;
for(int i1;igrid.length;i)
{
for(int j1;jgrid[i].length;i)
{
//如果grid[i][j]0则以[i][j]无法构成正方形,dp3[i][j]0;
if(grid[i][j]0)
{
dp3[i][j]0;
}else
{
//从[i][j]位置左边和上边寻找最小连续1的个数从而可以构成最大边长
maxsideMath.min(dp1[i][j],dp2[i][j]);
for(int imaxside;i0;i--)
{
//不断由最大变成找到最左边的位置[i][j-maxsize1]并且求解该位置竖向上方1的个数dp2[i][j-maxsize1],找到最上边的位置[i-maxsize1][j]并且求解该位置左边连续1的个数如果均大于maxsize表示能构成正方形否则继续缩小maxsize,不断进行寻找一旦找到满足条件的记录入dp3中并与maxsquare进行对比后break跳出循环
if(dp2[i][j-maxsize1]maxsizedp1[i-maxsize1][j]maxsize)
{
dp3[i][j]i*i;
maxsquareMath.max(maxsquare,dp3[i][j]);
break;
}
}
}
}
}
return maxsqure;
}
