利用前缀和计算二维矩阵子矩阵的和

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

利用前缀和计算二维矩阵子矩阵的和

  • 作者简介:一名后端开发人员,每天分享后端开发以及人工智能相关技术,行业前沿信息,面试宝典。
  • 座右铭:未来是不可确定的,慢慢来是最快的。
  • 个人主页:极客李华-CSDN博客
  • 合作方式:私聊+
  • 这个专栏内容:用最低价格鼓励和博主一起在寒假打卡高频大厂算法题,连续一个月,提升自己的算法实力,为了算法比赛或者春招。
  • 我的CSDN社区:https://bbs.csdn.net/forums/99eb3042821a4432868bb5bfc4d513a8
  • 微信公众号,抖音,b站等平台统一叫做:极客李华,加入微信公众号领取各种编程资料,加入抖音,b站学习面试技巧,职业规划

二维矩阵在计算机科学中具有重要的地位,它们广泛用于图形处理、数据处理以及算法设计等领域。在处理二维矩阵时,经常需要计算子矩阵的和。例如,给定一个 n * n 的矩阵,我们可能需要计算其中所有i * i子矩阵的和。

解决方案

为了高效地计算子矩阵的和,可以利用前缀和技术。通过预处理得到一个与原矩阵相同大小的二维数组,用于存储矩阵中每个位置左上角子矩阵的和。然后,利用前缀和数组可以在常数时间内计算任意子矩阵的和。

前缀和公式原理
p r e f i x S u m [ i ] [ j ] = p r e f i x S u m [ i − 1 ] [ j ] + p r e f i x S u m [ i ] [ j − 1 ] − p r e f i x S u m [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i][j] prefixSum[i][j]=prefixSum[i1][j]+prefixSum[i][j1]prefixSum[i1][j1]+a[i][j]

示例代码

下面是利用前缀和技术计算二维矩阵子矩阵和的示例代码:

#include <iostream>
using namespace std;

const int N = 4; // 矩阵的大小
int a[N + 1][N + 1] = {
    {0, 0, 0, 0, 0}, // 增加一行一列用于边界处理
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1}
};

int main() {
    // 计算前缀和
    int prefixSum[N + 1][N + 1];
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i][j];
        }
    }

    // 遍历所有可能的 i x i 子矩阵
    for (int i = 1; i <= N; ++i) {
        for (int x1 = 1; x1 <= N - i + 1; ++x1) {
            for (int y1 = 1; y1 <= N - i + 1; ++y1) {
                int x2 = x1 + i - 1;
                int y2 = y1 + i - 1;
                // 计算子矩阵的和
                int sum = prefixSum[x2][y2] - prefixSum[x2][y1 - 1] - prefixSum[x1 - 1][y2] + prefixSum[x1 - 1][y1 - 1];
                cout << "以 (" << x1 << ", " << y1 << ") 为左上角," << i << "x" << i << " 子矩阵的和为: " << sum << endl;
            }
        }
    }

    return 0;
}

运行结果:文章来源地址https://www.toymoban.com/news/detail-854851.html

以 (1, 1) 为左上角,1x1 子矩阵的和为: 1
以 (1, 2) 为左上角,1x1 子矩阵的和为: 0
以 (1, 3) 为左上角,1x1 子矩阵的和为: 1
以 (1, 4) 为左上角,1x1 子矩阵的和为: 0
以 (2, 1) 为左上角,1x1 子矩阵的和为: 0
以 (2, 2) 为左上角,1x1 子矩阵的和为: 1
以 (2, 3) 为左上角,1x1 子矩阵的和为: 0
以 (2, 4) 为左上角,1x1 子矩阵的和为: 1
以 (3, 1) 为左上角,1x1 子矩阵的和为: 1
以 (3, 2) 为左上角,1x1 子矩阵的和为: 0
以 (3, 3) 为左上角,1x1 子矩阵的和为: 1
以 (3, 4) 为左上角,1x1 子矩阵的和为: 0
以 (4, 1) 为左上角,1x1 子矩阵的和为: 0
以 (4, 2) 为左上角,1x1 子矩阵的和为: 1
以 (4, 3) 为左上角,1x1 子矩阵的和为: 0
以 (4, 4) 为左上角,1x1 子矩阵的和为: 1
以 (1, 1) 为左上角,2x2 子矩阵的和为: 2
以 (1, 2) 为左上角,2x2 子矩阵的和为: 2
以 (1, 3) 为左上角,2x2 子矩阵的和为: 2
以 (2, 1) 为左上角,2x2 子矩阵的和为: 2
以 (2, 2) 为左上角,2x2 子矩阵的和为: 2
以 (2, 3) 为左上角,2x2 子矩阵的和为: 2
以 (3, 1) 为左上角,2x2 子矩阵的和为: 2
以 (3, 2) 为左上角,2x2 子矩阵的和为: 2
以 (3, 3) 为左上角,2x2 子矩阵的和为: 2
以 (1, 1) 为左上角,3x3 子矩阵的和为: 5
以 (1, 2) 为左上角,3x3 子矩阵的和为: 4
以 (2, 1) 为左上角,3x3 子矩阵的和为: 4
以 (2, 2) 为左上角,3x3 子矩阵的和为: 5
以 (1, 1) 为左上角,4x4 子矩阵的和为: 8

到了这里,关于利用前缀和计算二维矩阵子矩阵的和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 二维前缀和公式 AcWing 796. 子矩阵的和

    记住两个公式就行 不知道算难还是算简单,公式就是代码里面写的那样,完完全全公式,没有任何其他东西

    2024年02月19日
    浏览(42)
  • 前缀和例题:子矩阵的和AcWing796-Java版

    //前缀和模板提,在读入数据的时候就可以先算好前缀和的大小 // 计算前缀的时候用 :g[i][j] = g[i][j-1] + g[i-1][j] - g[i-1][j-1] + Integer.parseInt(init[j-1]); // 计算结果的时候用 :g[x2][y2] - g[x1 - 1][y2]- g[x2][y1-1]   + g[x1 -1][y1 - 1] + \\\"n\\\" //一些重复加的地方都需要减掉,如计算前缀和的时候 g[i-1

    2024年02月02日
    浏览(41)
  • 前缀和--二维矩阵的前缀和

    原题链接 输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1,y1,x2,y2 ,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n,m,q 。 接下来 n 行,每行包含 m 个整数,表示整数矩阵。

    2024年01月16日
    浏览(41)
  • C++ 二维差分 二维前缀和逆运算 差分矩阵

    输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c ,其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c 。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数

    2024年02月21日
    浏览(52)
  • 【力扣】304. 二维区域和检索 - 矩阵不可变 <二维前缀和>

    给定一个二维矩阵 matrix ,以下类型的多个请求: 计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。 实现 NumMatrix 类: NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, co

    2024年02月10日
    浏览(38)
  • lintcode 1840 · 矩阵还原【中等 vip 二维前缀和数组】

    https://www.lintcode.com/problem/1840

    2024年02月04日
    浏览(41)
  • 《剑指 Offer》专项突破版 - 面试题 13 : 二维子矩阵的数字之和(C++ 实现)- 二维前缀和

    题目链接 :LCR 013. 二维区域和检索 - 矩阵不可变 - 力扣(LeetCode) 题目 : 输入一个二维矩阵,如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和?对于同一个二维矩阵,计算子矩阵的数字之和的函数可能由于输入不同的坐标而反复调用多次。 例如,对于下图中的二

    2024年01月18日
    浏览(39)
  • [USACO11MAR] Brownie Slicing G题解(二分+二维前缀和+矩阵分割)

    题目地址 P3017 [USACO11MAR] Brownie Slicing G 二分最大化最小值 切割思路: 一行一行进行切割,如果这一行可以切割出b块大于等于mid的块,就开始切割下一行 如果无法切割出b块,就把正在切割的行与下一行拼起来一起切割 最后通过能切割出b块的水平块块够不够a条来判断m是否合

    2024年02月07日
    浏览(38)
  • Matlab 获取矩阵的行数与列数 计算矩阵内所有元素的和

    有了行数与列数,可以进行对其矩阵所有元素求和 输出结果为 21

    2024年02月15日
    浏览(45)
  • JavaScript实现求1-100之间不能被3整除的数之和,求100以内偶数的和的两个程序代码

    以下为实现求1-100之间不能被3整除数之和求100以内偶数的和的两个程序代码和运行截图 目录 前言 一、实现输入两个数比较两个数的大小 1.1 运行流程及思想 1.2 代码段 1.3 JavaScript语句代码 1.4 运行截图 二、求100以内偶数的和 2.1 运行流程及思想 2.2 代码段 2.3 JavaScript语句代码

    2024年02月03日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包