购物网站建设款流程,天津建设工程信息网网上报名,潍坊市建设银行坊子支行网站,wordpress 镜像存储1139. 最大的以 1 为边界的正方形难度中等137收藏分享切换为英文接收动态反馈给你一个由若干 0 和 1 组成的二维网格 grid#xff0c;请你找出边界全部由 1 组成的最大 正方形 子网格#xff0c;并返回该子网格中的元素数量。如果不存在#xff0c;则返回 0。示例 1#xf…1139. 最大的以 1 为边界的正方形难度中等137收藏分享切换为英文接收动态反馈给你一个由若干 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 1001 grid[0].length 100grid[i][j] 为 0 或 1解题思路以正方形周长的路径扫描每个子网格 以当前坐标(i,j)为起点L为边长扫描一个正方形的周长判断是否构成一个正方形并不断更新maxL当前的最大边长最后返回maxL*maxL即可。AC代码class Solution {
public:bool hasSquare(int SI,int SJ,int L,vectorvectorint grid){// 扫描顺序上、右、下、左for(int k0;k4;k){if(k0){//上边for(int m0;mL;m){if(SJ0 || SJgrid[0].size())return false;if(grid[SI][SJ]!1)return false;if(mL-1)SJ;}}if(k1){//右边for(int m0;mL;m){if(SI0 || SIgrid.size())return false;if(grid[SI][SJ]!1)return false;if(mL-1)SI;}}if(k2){//下边for(int m0;mL;m){if(SJ0 || SJgrid[0].size())return false;if(grid[SI][SJ]!1)return false;if(mL-1)SJ--;}}if(k3){//左边for(int m0;mL;m){if(SI0 || SIgrid.size())return false;if(grid[SI][SJ]!1)return false;if(mL-1)SI--;}} }return true;}int largest1BorderedSquare(vectorvectorint grid) {if(grid.size()1){for(int i0;igrid[0].size();i){if(grid[0][i]1)return 1;}return 0;}//解题思路以正方形周长的路径扫描每个子网格int maxL0;int rowgrid.size(); //行数int colgrid[0].size(); //列数for(int i0;irow;i){for(int j0;jcol;j){if(grid[i][j]!1)continue;int Lmax(maxL,1);//以当前坐标(i,j)为起点L为边长扫描一个正方形的周长//判断是否构成一个正方形int LLenmin(row-i,col-j);bool isOkfalse;for(;LLLen;L){isOkhasSquare(i,j,L,grid);if(isOk)maxLmax(L,maxL);} }}return maxL*maxL;}
};
