1139. 最大的以 1 为边界的正方形
1.想法:
1.循环暴力
image.png循环遍历每个节点的值,当当前值为1的时候向左右扩散能找到的最大的边长
我们存在两个问题
例如:对于点(1,0) image.png
1.怎么确定最大边长
2.怎么确定这个最大边长所构成的正方形是合法的
对于第一个问题:我们可以从改点到行边界和竖边界找到最大的边长,如果不合法依次减一直到为0
对于第二个问题:我们可以以改点为左上顶点依次检测每个边是否合法
向右扩散到最右,向下边找到最大边长的上界.可以找到最大边长为min(向右,向下)
然后再去判断每条边是否合法
image.png
2.动态规划
//TODO
2.代码
class Solution {
public int largest1BorderedSquare(int[][] grid) {
int row = grid.length,col = grid[0].length,endX=0,endY=0,maxSide=0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j] == 1){
int disX = row-i;
int disY = col-j;
int side = disX>disY?disY:disX;
while(side>maxSide){
endX = i+side-1;
endY = j+side-1;
if(checkroute(grid,i,j,endX,endY)){
maxSide = side;
break;
}else{
side--;
}
}
}
}
}
return maxSide*maxSide;
}
private boolean checkroute(int[][] grid, int startX, int startY, int endX, int endY) {
//检测上左
int left = startX;
while(left<=endX){
if(grid[left++][startY]!=1)return false;
}
//检测左下
int leftDown = startY;
while(leftDown<=endY){
if(grid[startX][leftDown++]!=1)return false;
}
//检测右下
int rightDown = startY;
while(rightDown<=endY){
if(grid[endX][rightDown++]!=1)return false;
}
//检测下左
int downLeft = startX;
while(downLeft<=endX){
if(grid[downLeft++][endY]!=1)return false;
}
return true;
}
}
网友评论