题目大意：
统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 输出：7 解释： 边长为 1 的正方形有 6 个。 边长为 2 的正方形有 1 个。 正方形的总数 = 6 + 1 = 7.
提示：
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1277
解题思路分析：
解法一：动态规划
这又是一道动态规划DP，或者说是递归加记忆数组的题目。先不考虑0和1的限制，单纯考虑矩阵中的任意一点，以它为顶点向右下方能够构建出正方形的个数取决于，它到底边和右边的最小长度。假如最小长度为3的话，那么当前点就可以构建出3个正方形，边长分别为1，2和3。不过本题要求，不仅要构建出正方形，并且正方形内所有点都必须为1，这就需要使用到动态规划来思考问题。
对于任意一点，如果它的值为0，那么肯定无法构建出合理的正方形。如果为1时，先看它能构建出的所有格子都为1的最大正方形边长是多少，这个最大边长取决于当前点下方一格，右方一格，以及右下方一格能够构建出的合理正方形的最大边长，三个边长的最小值加一即为当前格子能够构建的最大边长。这样描述可能比较抽象，我们举个例子，看下图：
比如当前点是坐标为(1, 1)的浅蓝色格子，通过肉眼我们可以看出，当前格子下方(1, 2)能够构建出的最大合理正方形是红色边框区域，其边长为2，而当前格子右侧格子(2, 1)能画出的最大边长也为2，即深蓝色边框区域。最后右下点(2, 2)的最大边长为绿色区域，边长是3。因此，从(1, 1)点开始向右下方能构建出的最大正方形边长应该是min(2, 2, 3)+1，即3 (背景为黄色的区域)。
综上所述，在求某一点能够构建出的最大正方形边长时，我们可以从当前点开始递归，如果当前点为0，直接返回0，如果当前点是1，则：
f(x, y) = min(f(x+1, y), f(x, y+1), f(x+1, y+1))+1;
递归的终止条件为，当前点如果是在底边或者右边时，由于最多只能构建出1 x 1的正方形（没有足够的空间构建出更大的正方形），当前点的返回值应该为arr[x][y]。
最后，我们以每一个点作为起点计算出，以该点向右下能够构建出的最大正方形边长，所有结果的和即是返回结果。
实现代码：
Integer[][] memo; // 记忆数组
public int countSquares(int[][] matrix) {
memo=new Integer[matrix.length][matrix[0].length];
int res=0; // 返回结果
// 遍历所有点
// 求出以每一点为顶点向右下方能画出的最大正方形边长
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
// 求和
res+=help(matrix,i,j);
}
}
return res;
}
int help(int[][] matrix, int r, int c){
// 如果记忆数组不为空，直接返回
if(memo[r][c]!=null) return memo[r][c];
// 如果当前点在下边或者右边时，返回当前值
if(r==matrix.length-1||c==matrix[0].length-1){
return matrix[r][c];
}
// 如果当前点为0，直接返回0
if(matrix[r][c]==0) return 0;
// 下方格子能画出的最大正方形边长
int bottom = help(matrix, r+1,c);
// 右方格子能画出的最大正方形边长
int right = help(matrix, r,c+1);
// 右下方格子能画出的最大正方形边长
int bottomRight = help(matrix, r+1,c+1);
// 三者的最小值加一为当前返回结果
int res=Math.min(bottom,Math.min(right,bottomRight))+1;
memo[r][c]=res; // 将结果存入记忆数组
return res;
} 本题解法执行时间为12ms。
Runtime: 12 ms, faster than 47.17% of Java online submissions for Count Square Submatrices with All Ones.
Memory Usage: 58.2 MB, less than 100.00% of Java online submissions for Count Square Submatrices with All Ones.
解法二：前缀和
其实本题还有一个更加容易思考的解题思路。即使用前缀和来解题。我们需要首先对数组进行预处理，即统计出每一行以及每一列上的前缀和。统计前缀和的目的是，当我们想确定某一行或者某一列上某个区间内是否全是1，那么我们只要通过该行或者列的前缀和数组计算出该区间的和，然后查看该区间和是否等于区间长度即可。这一点会在接下来的思路中使用到。
解题时我们依旧使用二层循环来遍历数组中每一个点，如果当前点是0，跳过。如果当前点是1，返回结果加一（当前点自身是一个合理子矩阵），同时，我们以该点为起点，向右下方向各扩大一格（变为2*2的子矩阵），继续查看当前子矩阵是否都是1，此时我们无须重新遍历子矩阵中每一个点，只查看新增加的部分是否都是1即可。实际上新增的部分是当前子矩阵的最下一行以及最右一列，如果用代码来表示：
设k为从起点开始增加的边长。 新增行起始位置：matrix[当前行+k][当前列] 新增行终点位置：matrix[当前行+k][当前列+k] 新增列起始位置：matrix[当前行][当前列+k] 新增列终点位置：matrix[当前行+k][当前列+k]
我们使用前缀和数组可以轻松的计算出上述两个区间内1的个数，如果该个数等于区间长度，那么当前子矩阵为一个合理矩阵，返回结果加一，同时边长加一继续扩大子矩阵范围。反之，当前矩阵不合理，无须再继续扩大，退出当前循环，返回上层循环，继续查看矩阵中下一个点。重复上述过程，直到循环完矩阵中每一个点。
实现代码：
public int countSquares(int[][] matrix) {
// 每一行前缀和
int[][] presumPerRow=new int[matrix.length][matrix[0].length];
// 每一列前缀和
int[][] presumPerCol=new int[matrix.length][matrix[0].length];
for(int r=0;r<matrix.length;r++){
for(int c=0;c<matrix[0].length;c++){
if(c==0)presumPerRow[r][c]=matrix[r][c];
else presumPerRow[r][c]=presumPerRow[r][c-1]+matrix[r][c];
}
}
for(int c=0;c<matrix[0].length;c++){
for(int r=0;r<matrix.length;r++){
if(r==0)presumPerCol[r][c]=matrix[r][c];
else presumPerCol[r][c]=presumPerCol[r-1][c]+matrix[r][c];
}
}
int res=0; // 返回结果
// 循环每一点
for(int r=0;r<matrix.length;r++){
for(int c=0;c<matrix[0].length;c++){
// 当前点为0，跳过
if(matrix[r][c]==0) continue;
// 返回结果加一
res++;
// 以当前点为顶点向右下不断扩大边长。（注意不要越界）
for(int k=1;r+k<matrix.length&&c+k<matrix[0].length;k++){
int n1=presumPerRow[r+k][c+k]-(c==0?0:presumPerRow[r+k][c-1]);
if(n1!=k+1)break;
int n2=presumPerCol[r+k][c+k]-(r==0?0:presumPerCol[r-1][c+k]);
if(n2!=k+1)break;
res++;
}
}
}
return res;
} 本题解法执行时间为7ms。
Runtime: 7 ms, faster than 33.85% of Java online submissions for Count Square Submatrices with All Ones.
Memory Usage: 49.3 MB, less than 100.00% of Java online submissions for Count Square Submatrices with All Ones.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1277-count-square-submatrices-with-all-ones-解题思路分析/
View Comments (0)