1139. Largest 1-Bordered Square解题思路分析

题目大意:

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

给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。

示例 1:

输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:9
示例 2:

输入:grid = [[1,1,0,0]]
输出:1
 

提示:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] 为 0 或 1


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1139

解题思路分析:

这道题是要求出四周由1能够组成的最大正方形面积。注意只是边为1即可,中间的部分可以是1也可以是0。最简单的思路就是暴力算法,以每一个点为顶点,向右侧和下侧画正方形,正方形的边长由1到左侧或者下侧的边界为止逐个循环,如果正方形四边上的数字和与边长相同,则他是符合题目要求的一个候选解,直到循环结束即可遍历出最优答案。

这里需要使用到三层循环,横坐标纵坐标各需要一层,循环正方形边长需要一层,这样运行时间上很可能会超时。因此我们需要做一些优化和剪枝。首先以0为顶点的正方形肯定是不合法的,直接略过,另外,在计算边长时,我们可以使用preSum前缀和的方式提前做好计算,方便快速的得到任意两点间的距离,减少重复计算。

看下完整代码:

public int largest1BorderedSquare(int[][] grid) {
    int[][] memo_r = new int[grid.length][grid[0].length]; // 横向前缀和
    int[][] memo_c = new int[grid.length][grid[0].length]; // 纵向前缀和
    for(int r=0;r<grid.length;r++){
        for(int c=0;c<grid[0].length;c++){
            if(c==0){
                memo_c[r][c] = grid[r][c];
            }else{
                memo_c[r][c] = memo_c[r][c-1] + grid[r][c];
            }
            if(r==0){
                memo_r[r][c] = grid[r][c];
            }else{
                memo_r[r][c] = memo_r[r-1][c] + grid[r][c];
            }
        }
    }
    int res = 0; // 结果
    for(int r=0;r<grid.length;r++){ // 循环纵坐标
        for(int c=0;c<grid[0].length;c++){ // 循环横坐标
            int value = grid[r][c]; // 当前点
            if(value==0){ // 顶点为0直接略过
                continue;
            }
            // 防止正方形越界,计算当前点到底边和右边的最小值作为正方形最大边长。
            int maxLength = Math.min(grid.length - r, grid[0].length - c);
            for(int i = 0; i<maxLength;i++){
                int top = memo_r[r+i][c] - memo_r[r][c] + value;
                int bottom = memo_r[r+i][c+i] - memo_r[r][c+i] + value;
                int left = memo_c[r][c+i] - memo_c[r][c] + value;
                int right = memo_c[r+i][c+i] - memo_c[r+i][c] + value;
                // 四条边之和是否等于周长
                if(top+bottom+left+right == (i+1) * 4){
                    res = Math.max(res, (i+1)*(i+1)); // 更新结果
                }
            }
        }
    }
    return res;
}

本解法用时16ms。效率不高但可以通过。二刷时再考虑更优解法。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/1139-largest-1-bordered-square解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。