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)


相关推荐

  • 安防基础知识

    安防基础知识一、目前安防视频监控的普遍现状:1,前端主要以模拟摄像机为主。模拟摄像机的天生弊端 导致监控录像画质无法超越D1。2,模拟信号收到电磁干扰,画面常常有雪花噪点和干扰条纹等。3,监控录像的噪点与干扰导致录像码流(硬盘消耗)浪费。4,模拟监控布线多而繁琐。

  • 【转贴】Render RenderContents RenderControl 三个方法的区别

    【转贴】Render RenderContents RenderControl 三个方法的区别每个页面都有一个控件树,代表本页面所拥有的所有子控件,页面控件就是控件树的根,为了生成控件树,页面将建立一个HtmlTextWriter类的实例,在这个实例中封装了相应流,接着页面会把HtmlText

  • iptable 理解

    iptable 理解这个当初我理解不了,主要是没把netfilter理解清楚。Netfilter是集成在内核中的,用来定义存储各种规则的。Iptalbe是修改这些规则的工具,修改后存在netfilter里面。数据包进入LINUX服务器时,先进入服务器的netfilter模块中进行判断处理。 Netfilter包含有三种表,三种表下共包含有五种链,链下面包含各种规则。即表包含若干链,链包含若干规则。 …

  • linux下system函数错误返回-1 错误原因NO child processes

    linux下system函数错误返回-1 错误原因NO child processes调用system函数执行一个shell命令,返回-1,错误提示nochildprocesses但system可以执行成功原因是调用system之前有放置忽略SIGCHLD的语句signal(SIGCHLD,SIG_IGN);如果SIGCHLD信号行为被设置为SIG_IGN时,waitpid()函数有可能因为找不到子进程而报ECHILD错误。似乎我们找到了问题的解决方案:在调用s…

  • Murmur下载_highwayhash

    Murmur下载_highwayhashpackageorg.videolan.vlc;/**Murmurhash2.0.**Themurmurhashisarelativefasthashfunctionfrom*http://murmurhash.googlepages.com/forplatformswithefficient*multiplication.**Thisisare-i…

    2022年10月19日
  • 计算机网络-常见洪水攻击「建议收藏」

    计算机网络-常见洪水攻击「建议收藏」什么是洪水攻击洪水攻击(FLOODATTACK)是指利用计算机网络技术向目标主机发送大量无用的数据报文,使得目标主机忙于处理无用的数据报文而无法提供正常服务的网络行为。主要原理:利用了网络协议中安

发表回复

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

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