大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给你一个 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
题解
参考上一篇博客添加链接描述
这里只需要把每个以[i , j]为右下角的矩形统计出来有多少个就行了。
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int n = matrix.size(),m = matrix[0].size();
int res = 0;
vector<vector<int> >f(n + 1,vector(m + 1,0));
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
if(matrix[i - 1][j - 1] == 1){
f[i][j] = min(f[i - 1][j],min(f[i][j - 1],f[i - 1][j - 1])) + 1;
}
else f[i][j] = 0;
res += f[i][j];
}
}
return res;
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168637.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...