美文网首页
1139. 最大的以 1 为边界的正方形

1139. 最大的以 1 为边界的正方形

作者: 最困惑的时候就是能成长的时候 | 来源:发表于2019-08-12 16:46 被阅读0次

    1139. 最大的以 1 为边界的正方形

    1.想法:

    1.循环暴力

    image.png

    循环遍历每个节点的值,当当前值为1的时候向左右扩散能找到的最大的边长

    我们存在两个问题
    1.怎么确定最大边长
    2.怎么确定这个最大边长所构成的正方形是合法的
    对于第一个问题:我们可以从改点到行边界和竖边界找到最大的边长,如果不合法依次减一直到为0
    对于第二个问题:我们可以以改点为左上顶点依次检测每个边是否合法

    例如:对于点(1,0) image.png
    向右扩散到最右,向下边找到最大边长的上界.可以找到最大边长为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;
        }
    }
    

    相关文章

      网友评论

          本文标题:1139. 最大的以 1 为边界的正方形

          本文链接:https://www.haomeiwen.com/subject/kciujctx.html