给你一个 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 <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
Related Topics
数组
动态规划
矩阵
思路1：判断每一个起点所构成的正方形分析：怎样才能构成正方形？
经过判断，正方形都是从某个起点[i,j]为1开始，向右和向下扩展一行到[i+1,j+1]，而且下面这一行和这一列范围内都必须要为1。
算法思路：
从每个点开始，如果为1，就开始判断以这个点为起点的正方形。使用fun方法。
fun方法思路：判断以(i,j)为起点的正方形个数
首先这个点为1，是一个正方形，初始化正方形个数sum为1.还需要保存这个起点[startI,StartJ].
因为正方形每次都是向右向下增加一行。endI和endJ自增加1后
向下一行的为第endI行的第[startJ,endJ]列范围是否为1
向右一列为第endJ列的第[startI,endI]行是否为1.
如果都为1 ，则正方形个数加1，不为1直接返回结果。
class Solution {
public int countSquares(int[][] matrix) {
int sum = 0;
int m = matrix.length;
int n = matrix[0].length;
for(int i = 0 ; i < m;i++){
for(int j = 0 ; j < n;j++){
if(matrix[i][j]==1){
sum+=fun(matrix,i,j);
}
}
}
return sum;
}
public int fun(int[][] matrix,int endI,int endJ){
//以元素[i,j]为起点，每次向右和向下扩展
int m = matrix.length;
int n = matrix[0].length;
int sum = 1;
int startI = endI;
int startJ = endJ;
while(endI < m-1 && endJ < n-1){
//需要判断第i+1行和第j+1元素
endI++;
endJ++;
//判断i+1行的第[startJ,endJ]列范围内是否为1
for(int j = startJ; j <= endJ;j++){
if(matrix[endI][j]!=1){
return sum;
}
}
//判断j+1列的第[startI,endI]行范围内是否为1
for(int i = startI; i <= endI;i++){
if(matrix[i][endJ] != 1){
return sum;
}
}
sum++;
}
return sum;
}
}
解答成功:
执行耗时:6 ms,击败了85.09% 的Java用户
内存消耗:49.4 MB,击败了83.69% 的Java用户
思路2：动态规划
具体分析参考leetcode。
dp[i] [j]表示以i，j为右下角的正方形的边长(即就是以i，j为右下角的正方形个数)。
那么第一行和第一列的dp值就等于matrix自身的值。
如果matrix的值等于0，直接就为0.
如果matrix的值等于1，dp[i] [j] = min(dp[i-1] [j],dp[i-1] [j-1],dp[i] [j-1])+1。
即就是当前元素的左边和上边还有左上角的位置的最小值。
分析：为什么是左边和上边还有左上角位置的最小值呢？
假设：
以（i，j）为右下角的正方形的dp为4，那么这三个位置的正方形个数最少为3
dp[i-1] [j] >= 3 = dp[i] [j] -1
dp[i-1] [j-1] >= 3 = dp[i] [j] -1
dp[i] [j-1] >= 3 = dp[i] [j] -1
推出：dp[i] [j] <= min(dp[i-1] [j],dp[i-1] [j-1],dp[i] [j-1])+1。
以(i-1,j)、(i,j-1)、(i-1,j-1)的最小值为3,那么(i,j)的正方形个数至少为4
dp[i-1] [j] + 1 <= dp[i] [j]
dp[i-1] [j-1] <= dp[i] [j]
dp[i] [j-1] <= dp[i] [j]
推出 dp[i] [j] >= min(dp[i-1] [j],dp[i-1] [j-1],dp[i] [j-1])+1
所以 dp[i] [j] >= min(dp[i-1] [j],dp[i-1] [j-1],dp[i] [j-1])+1
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int sum = 0;
for(int i = 0; i < m;i++){
for(int j = 0 ; j < n;j++){
//处理第一行和第一列
if(i == 0 || j == 0){
dp[i][j] = matrix[i][j];
}else if(matrix[i][j] == 0){
dp[i][j] = 0;
}else{
dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
}
sum+=dp[i][j];
}
}
return sum;
}
}
解答成功:
执行耗时:7 ms,击败了41.93% 的Java用户
内存消耗:50 MB,击败了74.69% 的Java用户
总结：
思路1是从左上角往下计算，需要每次判断一行和一列是否都为1.
思路2是从右上角往左上角判断，可以根据已知的计算内容判断当前节点，使用动态规划。
