C++刷leetcode（1277. 统计全为 1 的正方形子矩阵）【动态规划】

糖逗

题目描述：

1. 给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入：matrix =
   
8. [
   
9.   [0,1,1,1],
   
10.   [1,1,1,1],
    
11.   [0,1,1,1]
    
12. ]
    
13. 输出：15
    
14. 解释：
    
15. 边长为 1 的正方形有 10 个。
    
16. 边长为 2 的正方形有 4 个。
    
17. 边长为 3 的正方形有 1 个。
    
18. 正方形的总数 = 10 + 4 + 1 = 15.
    
19. 示例 2：
    
20. 
    
21. 输入：matrix =
    
22. [
    
23.   [1,0,1],
    
24.   [1,1,0],
    
25.   [1,1,0]
    
26. ]
    
27. 输出：7
    
28. 解释：
    
29. 边长为 1 的正方形有 6 个。
    
30. 边长为 2 的正方形有 1 个。
    
31. 正方形的总数 = 6 + 1 = 7.
    
32.  
    
33. 
    
34. 提示：
    
35. 
    
36. 1 <= arr.length&#160;<= 300
    
37. 1 <= arr[0].length&#160;<= 300
    
38. 0 <= arr[i][j] <= 1
    
39. 
    
40. 来源：力扣（LeetCode）
    
41. 链接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones
    
42. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int countSquares(vector<vector<int>>& matrix) {
   
4.         int res = 0;
   
5.         int len1 = matrix.size(), len2 = matrix[0].size();
   
6.         for(int i = 0 ; i < len1; i++){
   
7.             for(int j = 0 ; j < len2; j++){
   
8.                 if(matrix[i][j] == 0) continue;
   
9.                 else if(i == 0 || j == 0) res++;
   
10.                 else{
    
11.                     matrix[i][j] = min(matrix[i - 1][j - 1],min(matrix[i - 1][j],matrix[i][j - 1])) + 1;
    
12.                     res += matrix[i][j];
    
13.                 }
    
14.             }
    
15.         }
    
16.         return res;
    
17. 
    
18.     }
    
19. };

复制代码

参考题解：https://leetcode-cn.com/problems ... i-jie-fa-by-52hz-r/

糖逗

221. 最大正方形
题目描述：

1. 
   
2. 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
   
3. 
   
4. 示例:
   
5. 
   
6. 输入:
   
7. 
   
8. 1 0 1 0 0
   
9. 1 0 1 1 1
   
10. 1 1 1 1 1
    
11. 1 0 0 1 0
    
12. 
    
13. 输出: 4

复制代码

1. class Solution {
   
2. public:
   
3.     int maximalSquare(vector<vector<char>>& matrix) {
   
4.         int res = 0;
   
5.         if(matrix.size() == 0) return res;
   
6.         int len1 = matrix.size(), len2 = matrix[0].size();
   
7.         vector<vector<int> > dp(len1, vector<int>(len2, 0));
   
8.         for(int i = 0; i < len1; i ++){
   
9.             for(int j = 0; j < len2; j++){
   
10.                 if(matrix[i][j] == '0') dp[i][j] = 0;
    
11.                 else if(i == 0 || j == 0) dp[i][j] = 1;
    
12.                 else{
    
13.                     dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;  
    
14.                 }
    
15.                 res = max(res, dp[i][j]);
    
16.             }
    
17.         }
    
18.         return res*res;
    
19. 
    
20.     }
    
21. };

复制代码

糖逗

相同类型题