1277. 统计全为 1 的正方形子矩阵(动态规划)

1277. 统计全为 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],

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)


相关推荐

  • JAVA留言板_java项目实例源码

    JAVA留言板_java项目实例源码java实现简单留言板功能的代码实例数据库对应的表:guestbook:id,name,phone,email,title,content,time;id新建webproject:guestbookbuildPath:引入连接数据库的驱动的类库在webRoot目录中加入:+faceditor+jsweb.xml代码:xmlns=”http://java….

  • c# dynamic用法_dynamic_cast详解

    c# dynamic用法_dynamic_cast详解dynamic是FrameWork4.0的新特性。dynamic的出现让C#具有了弱语言类型的特性。编译器在编译的时候不再对类型进行检查,编译期默认dynamic对象支持你想要的任何特性。比如,即使你

  • iOS: 学习笔记, Swift与C指针交互(译)

    iOS: 学习笔记, Swift与C指针交互(译)

    2021年12月14日
  • Jedis 连接Redis 集群[通俗易懂]

    Jedis 连接Redis 集群[通俗易懂]1.Jedis实现了连接Redis集群的操作,但是操作Redis集群的API是JedisCluster,和单机版api不一致(Jedis);2.创建JedisCluster需要一个Set集合,Set集合的每一个元素是HostAndPort;JedisCluster实际上可以根据一个节点的IP和端口号自动发现集群中的其它节点;代码:packagecom.etoak;importredis.clients.jedis.HostAndPort;importredis.client

  • UCOSII操作系统学习之任务间的通信(1)

    UCOSII操作系统学习之任务间的通信(1)1.任务间通讯方式:信号量和邮箱为了把描述事件的数据结构统一起来,UCOSII使用叫做事件控制块(ECB)的数据结构来描述诸如信号量、邮箱(消息邮箱)和消息队列这些事件。信号量,邮箱,消息队列都是一类事件。2.信号量:1)创建信号量OS_EVENT*OSSemCreate(INT16Ucnt)…

  • BoundsChecker 使用方法[通俗易懂]

    1前言我在本文中详细介绍了测试工具NuMegaDevpartner(以下简称NuMega)的使用方法。NuMega是一个动态测试工具,主要应用于白盒测试。该工具的特点是学习简单、使用方便、功能有效。NuMega共有三个独立的子功能——BoundsChecker、TrueCoverage、TrueTime。BoundsChecker为代码检错工具,TrueCoverage为测试覆盖率统计…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号