【算法思考记录】【前缀和,C++】力扣1277. 统计全为 1 的正方形子矩阵

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

原题链接


使用前缀和算法解决统计全为1的正方形子矩阵问题

题目分析

题目要求我们统计在一个由0和1构成的矩阵中,所有完全由1组成的正方形子矩阵的数量。这是一道中等难度的算法题目,其关键在于高效地计算出不同大小的正方形子矩阵是否完全由1组成。

解题思路

解决此问题的一个有效方法是使用前缀和算法。前缀和是一种预处理技术,通过计算数组中每个元素对应的前缀和,可以快速计算出任意子数组的和。在这个问题中,我们将前缀和算法扩展到二维,以便快速计算任意子矩阵的元素和。

前缀和算法的基本原理

前缀和算法是一种用于快速求解数组或矩阵中某个区间内元素和的技术。这种方法特别适用于需要多次对同一数据集的不同区间求和的情况。它通过预处理数据来优化求和的效率。

一维前缀和

假设我们有一个一维数组 arr,其前缀和数组 preSum 可以这样计算:

  1. 初始化 preSum[0] = 0
  2. 对于 arr 中的每个元素 arr[i],计算 preSum[i+1] = preSum[i] + arr[i]

这样,preSum[i] 存储了 arr 中从第一个元素到第 i-1 个元素的总和。如果我们想要计算 arr 中从第 l 个元素到第 r 个元素的和,我们只需要计算 preSum[r+1] - preSum[l]

二维前缀和

二维前缀和是一维前缀和的扩展,用于处理矩阵。假设我们有一个二维数组 matrix,其对应的二维前缀和矩阵 preSum 可以这样计算:

  1. 初始化 preSum 的所有元素为0。
  2. 对于 matrix 中的每个元素 matrix[i][j],计算 preSum[i+1][j+1] 的值。这个值等于其左侧元素的前缀和、上方元素的前缀和和左上方元素的前缀和的总和,再减去左上方元素的前缀和,最后加上 matrix[i][j] 本身的值。

计算矩阵中某个子矩形区域内元素的总和时,设该区域的左上角坐标为 (r1, c1),右下角坐标为 (r2, c2),则该区域内元素的总和可以表示为:

preSum[r2][c2] - preSum[r1-1][c2] - preSum[r2][c1-1] + preSum[r1-1][c1-1]

这个公式的含义是:从整个矩阵的起点到 (r2, c2) 的总和,减去上方和左方的部分重叠的区域,再加上左上角重复减去的部分。

应用

在解决我们的问题时,我们利用了二维前缀和算法来快速计算矩阵中任意正方形区域内的元素总和。通过这种方式,我们避免了对每个可能的正方形区域进行繁琐的重复计算,显著提高了算法的效率。

代码实现

以下是基于前缀和算法的解决方案,包含详细的注释说明。

#include <vector>
using namespace std;

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // 使用二维数组pre_sum存储前缀和
        vector<vector<int>> pre_sum(m + 1, vector<int>(n + 1));

        // 构建前缀和矩阵
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                pre_sum[i + 1][j + 1] = pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j] + matrix[i][j];
            }
        }

        int ans = 0;
        // max_edge为可能的最大正方形边长
        int max_edge = min(m, n);

        // 遍历所有可能的正方形大小和位置
        for (int k = 1; k <= max_edge; ++k) {
            for (int i = k; i <= m; ++i) {
                for (int j = k; j <= n; ++j) {
                    // 计算正方形的左上角和右下角坐标
                    int r1 = i - k, c1 = j - k;
                    int r2 = i, c2 = j;
                    // 计算正方形内部的元素和
                    long long actual = 0LL + pre_sum[r2][c2] - pre_sum[r1][c2] - pre_sum[r2][c1] + pre_sum[r1][c1];
                    // 如果和等于正方形面积,则说明该正方形完全由1组成
                    if (actual == k * k) {
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

算法解析

  1. 初始化前缀和矩阵:我们创建一个二维数组pre_sum来存储原矩阵的前缀和。pre_sum[i + 1][j + 1]表示原矩阵左上角到(i, j)位置形成的矩形区域内所有元素的和。

  2. 计算前缀和:通过遍历原矩阵,利用pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + matrix[i-1][j-1]公式计算每个位置的前缀和。

  3. 遍历所有可能的正方形:我们遍历所有可能的正方形大小和起始位置,利用前缀和快速计算正方形内部的元素和。

  4. 统计符合条件的正方形:对于每个正方形,如果其内部元素和等于其面积(即边长的平方),则说明这个正方形完全由1组成,计数器ans增加。

  5. 返回结果:最后返回计数器

ans,即为完全由1组成的正方形子矩阵的总数。

结论

通过使用前缀和算法,我们能够有效地解决这个问题,减少了重复计算,提高了算法的效率。这种方法在处理涉及子数组或子矩阵和的问题时非常有用。文章来源地址https://www.toymoban.com/news/detail-775093.html

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

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

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

相关文章

  • 【算法思考记录】动态规划入门!力扣2606. 找到最大开销的子字符串【Python3、动态规划】

    原题链接 动态规划(Dynamic Programming,简称 DP)是一种通过将原问题分解为相互重叠的子问题并只解决一次的方法来解决问题的算法优化技术。动态规划通常用于优化递归问题,通过存储子问题的解来避免重复计算,从而显著提高算法的效率。 动态规划的基本思想是将原问题

    2024年02月03日
    浏览(44)
  • 蓝桥杯统计子矩阵前缀和C++(附图文超详细讲解)(保姆级)

    给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?  第一行包含三个整数 N, M 和 K.  之后 N 行每行包含 M 个整数,代表矩阵 A. 一个整数代表答案。 满足条件的子矩阵一共有 19,包含: 大小为 1 × 1 的有

    2023年04月08日
    浏览(39)
  • leetcode 统计全为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 个

    2024年02月08日
    浏览(47)
  • C++前缀和算法:构造乘积矩阵

    C++算法:前缀和基础 给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ,定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件,则称 p 为 grid 的 乘积矩阵 : 对于每个元素 p[i][j] ,它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

    2024年02月08日
    浏览(49)
  • C++基础算法前缀和和差分篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了前缀和和差分算法 Ⅵ .Ⅰ前缀和 ① 一维前缀和 : ​ 就是构建一个新的数组 s ,用来存储另一个数组的和前 i 个数组元素的和。用公式表达就是: S [ i ] = a [ 0 ]

    2024年02月16日
    浏览(51)
  • C++排序、前缀和算法的应用:英雄的力量

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 排序 英雄的力量 给你一个下标从 0 开始的整数数组 nums ,它表示英雄的能力值。如果我们选出一部分英雄,这组英雄的 力量 定义为: i0 ,i1 ,… ik 表示这组英雄在数组中的下标。那么这组英雄

    2024年02月06日
    浏览(75)
  • C++前缀和算法:生成数组原理、源码及测试用例

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 动态规划,日后完成。 给定三个整数 n、m 和 k 。考虑使用下图描述的算法找出正整数数组中最大的元素。 请你构建一个具有以下属性的数组 arr : arr 中包含确切的 n 个整数。 1 = arr[i] = m 其中 (

    2024年02月06日
    浏览(44)
  • C++前缀和算法的应用:摘水果 原理源码测试用例

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ,其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列

    2024年02月06日
    浏览(40)
  • 【力扣·每日一题】2085.统计出现过一次的公共字符串(模拟 哈希表 优化 C++ Go)

    题目链接 给你两个字符串数组 words1 和 words2 ,请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。 输入:words1 = [“leetcode”,“is”,“amazing”,“as”,“is”], words2 = [“amazing”,“leetcode”,“is”] 输出:2 解释: “leetcode” 在两个数组中都恰好出现一次,计入答

    2024年01月21日
    浏览(49)
  • C++前缀和算法的应用:石头游戏 VIII 原理源码测试用例

    C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 Alice 和 Bob 玩一个游戏,两人轮流操作, Alice 先手 。 总共有 n 个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1 ,他将执行以下操作: 选择一个整数 x 1 ,并且 移除 最左边的 x

    2024年02月08日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包