专栏首页刷题笔记【leetcode第 165 场周赛】统计全为 1 的正方形子矩阵

【leetcode第 165 场周赛】统计全为 1 的正方形子矩阵

版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/103334424

5277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15. Example 2:

Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300 1 <= arr[0].length <= 300 0 <= arr[i][j] <= 1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

暴力破解

选好一个起点,每个数都会当一次起点

然后从起点开始,一圈一圈往外扩展,扩展一圈就+1

直到遇到0,就结束扩展,更换下一个起点,遍历所有起点需要 N*M,然后每个起点最多查询N*M的信息,所以复杂度就是 N*M*N*M

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int count=0;
        int x = matrix.size();
        int y = matrix[0].size();

        for(int a=0;a<x;a++){
            for(int b=0;b<y;b++){
                int flag=1;
                for(int t=0;b+t<y&&a+t<x;t++){
                    for(int l=0;l<=t;l++){
                        flag=flag&matrix[a+t][b+l]&&matrix[a+l][b+t];
                    }
                    flag=flag&matrix[a+t][b+t];
                    if(flag){
                        //cout<<a<<b<<t<<endl;
                        count++;
                    }else{
                        break;
                    }
                }
            }
        }
        return count;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】最长公共前缀

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【HBUOJ】阿生的小球

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【Leet Code】22. Generate Parentheses

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • LeetCode-52-N-Queens-II

    只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

    小二三不乌
  • 百炼1005

    用户7727433
  • 杭电2010

    用户7727433
  • 问题:单片机软件仿真和实际运行速度不一样?

    如图,问题大概就是说初学单片机,用软件仿真出来的程序,在开发板上运行的效果比仿真的快,晶振都是一样的12M。还问到一个1T模式和12T模式的区别?

    单片机技术宅
  • WPF效果第一百二十八篇之折叠动画

    马上就要回家了,手上也没啥工作了;这不又发现了一个不错的效果:窗口的折叠动画效果;咱们直接来看看最终效果:

    WPF程序员
  • 3+2 定位与5轴联动到底有什么区别?

    在一个三轴铣削程序执行时,使用五轴机床的两个旋转轴将切削刀具固定在一个倾斜的位置,3+2加工技术的名字也由此而来,这也叫做定位五轴机床,因为第四个轴和第五个轴是...

    UG数控编程
  • 并查集(union-find sets)

    一.并查集及其优化 - 并查集:由若干不相交集合组成,是一种简单但是很好用的数据结构,拥有优越的时空复杂性,一般用于处理一些不相交集合的查询和合并问题。 ...

    Enterprise_

扫码关注云+社区

领取腾讯云代金券