1277. 统计全为 1 的正方形子矩阵

这篇具有很好参考价值的文章主要介绍了1277. 统计全为 1 的正方形子矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1277. 统计全为 1 的正方形子矩阵


题目链接:1277. 统计全为 1 的正方形子矩阵

代码如下:文章来源地址https://www.toymoban.com/news/detail-833998.html

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        if(matrix.size()==0||matrix[0].size()==0)   return 0;

        //dp[i][j]代表以(i,j)为右下角,且只包含1的正方形边长的最大值
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
        int total=0;

        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                if(matrix[i][j]==1)
                {
                    if(i==0||j==0)
                        dp[i][j]=1;
                    else
                        dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    if(dp[i][j]!=0)
                        total+=dp[i][j];
                }
                    
            }
        }
        return total;
    }
};

到了这里,关于1277. 统计全为 1 的正方形子矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode-221. 最大正方形

    题目来源 221. 最大正方形 现在我们需要找到只包含 ‘1’ 的最大正方形。首先,我们可以初始化一个和原始矩阵相同大小的矩阵 dp,用来记录每个格子所在的最大正方形的边长。 对于第一行和第一列的格子,它们的 dp 值只能是 0 或 1,因为它们的左侧或上侧没有格子。我们

    2023年04月11日
    浏览(34)
  • 【LeetCode-中等】221. 最大正方形(详解)

    在一个由  \\\'0\\\'  和  \\\'1\\\'  组成的二维矩阵内,找到只包含  \\\'1\\\'  的最大正方形,并返回其面积。 力扣原题链接   暴力法一般不是最优解,但是可以拿来练手 由于正方形的面积等于边长的平方,因此要找到最大正方形的面积,首先需要找到最大正方形的边长,然后计算最大边

    2024年02月13日
    浏览(41)
  • 将正方形矩阵顺时针转动 90°

    【题目】 给定一个 N×N 的矩阵 matrix,把这个矩阵调整成顺时针转动 90°后的形式。 例如: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 顺时针转动 90°后为: 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 【要求】 额外空间复杂度为 O(1)。 思路: 这里使用分圈处理的方式,在矩阵中用左上角的坐标(tR,tC)和

    2024年02月13日
    浏览(28)
  • leetcode473. 火柴拼正方形(回溯算法-java)

    难度 - 中等 原题链接 - leetcode473 火柴拼正方形 你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次 。 如果你能使这个正

    2024年02月12日
    浏览(27)
  • LeetCode221.Maximal-Square<最大正方形>

        这题是动态规划,但是不会写。想着判断dp的 上,左,左上  去了。发现只能这样最大只能判断面积为4的正方形因为只会判断另外三个方格。而要想判断更大的正方形那就需要递归操作了。那肯定会超时了。 好吧,只能看答案了。 正方形的面积的长乘宽。在例子中我们

    2024年02月15日
    浏览(29)
  • 【LeetCode热题100】打卡第39天:数组中第K个最大元素&最大正方形

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月16日
    浏览(36)
  • Python-彩色正方形

    核心代码 核心代码 核心代码

    2024年02月19日
    浏览(30)
  • python绘制螺旋正方形

    1.首先导入画图功能库turtle 2.设置画笔大小,颜色  turtle.pensize()  turtle.pencolor() 3.如何绘制:螺旋正方形一开始外边有3条长度相同的边,先勾勒出一条边循环3次将外边构出,里边每勾勒一条循环两次,再进行循环,即需要一个双循环,边每次比前一次缩短。 画笔前进  turt

    2024年04月15日
    浏览(35)
  • CSS 3D旋转正方形

    2024年01月23日
    浏览(31)
  • P1387 最大正方形 题解

    通过二维前缀和判定矩形内是否全为1,计算和等于长度的平方就判断为是 复杂度 (Theta (n^2log{n})) 设状态 (f_{i,j}) 为以第 (i) 行 (j) 列为右下角的最大正方形的边长, (a_{i,j}) 表示输入矩阵中的数值,有转移方程: [f_{i,j} = (min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}) + 1) * a_{i,j}] 解释:

    2024年02月16日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包