网站模板 单页,龙凤网站建设云聚达,东莞常平有高铁站吗,开网店需要了解的流程题目链接 Leetcode.1139 最大的以 1 为边界的正方形 Rating #xff1a; 1744 题目描述
给你一个由若干 0 和 1 组成的二维网格 grid#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格#xff0c;并返回该子网格中的元素数量。
如果不存在#xff0c;则返回 0。…题目链接 Leetcode.1139 最大的以 1 为边界的正方形 Rating 1744 题目描述
给你一个由若干 0 和 1 组成的二维网格 grid请你找出边界全部由 1 组成的最大 正方形 子网格并返回该子网格中的元素数量。
如果不存在则返回 0。
示例 1 输入grid [[1,1,1],[1,0,1],[1,1,1]] 输出9 示例 2 输入grid [[1,1,0,0]] 输出1 提示
1grid.length1001 grid.length 1001grid.length1001grid[0].length1001 grid[0].length 1001grid[0].length100grid[i][j]为 0 或 1
分析
使用 dp 求解我们定义 f(i,j,0)和f(i,j,1)f(i,j,0)和f(i,j,1)f(i,j,0)和f(i,j,1)分别为以点 (i,j)结尾向左 和 向上的连续 1的个数。
在f(i,j,0)0和f(i,j,1)0f(i,j,0) 0和f(i,j,1) 0f(i,j,0)0和f(i,j,1)0 的情况下我们取 dmin(f(i,j,0),f(i,j,1))d min(f(i,j,0),f(i,j,1))dmin(f(i,j,0),f(i,j,1))。
遍历kkk (0kd)(0kd)(0kd)判断 f(i−k1,j,0)k和f(i,j−k1,1)kf(i-k1,j,0) k 和 f(i,j-k1,1) kf(i−k1,j,0)k和f(i,j−k1,1)k如果条件成立说明可以构成一个最后一点是 (i,j)边长为 k的正方形。
时间复杂度O(m∗n∗min(m∗n))O(m*n*min(m*n))O(m∗n∗min(m∗n))
C代码
class Solution {
public:int largest1BorderedSquare(vectorvectorint grid) {int m grid.size(),n grid[0].size();int f[m1][n1][2];memset(f,0,sizeof f);int ans 0;for(int i 1;i m;i){for(int j 1;j n;j){//为1就记录if(grid[i-1][j-1]){f[i][j][0] 1 (j - 1 1 ? f[i][j-1][0] : 0);f[i][j][1] 1 (i - 1 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] 0 f[i][j][1] 0){int d min(f[i][j][0],f[i][j][1]);//倒序判断能构成正方形的最大边长for(int k d;k 0;k--){if(i-k1 1 j-k1 1 f[i-k1][j][0] k f[i][j-k1][1] k){ans max(ans,k*k);break;}}}}}return ans;}
};Java代码
class Solution {public int largest1BorderedSquare(int[][] grid) {int m grid.length,n grid[0].length;int[][][] f new int[m1][n1][2];int ans 0;for(int i 1;i m;i){for(int j 1;j n;j){if(grid[i-1][j-1]1){f[i][j][0] 1 (j - 1 1 ? f[i][j-1][0] : 0);f[i][j][1] 1 (i - 1 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] 0 f[i][j][1] 0){int d Math.min(f[i][j][0],f[i][j][1]);for(int k d;k 0;k--){if(i-k1 1 j-k1 1 f[i-k1][j][0] k f[i][j-k1][1] k){ans Math.max(ans,k*k);break;}}}}}return ans;}
}
