[LeetCode] Range Sum Query 2D - Immutable 二维区域和检索 - 不可变

简介:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

这道题让我们求一个二维区域和的检索,是之前那道题Range Sum Query - Immutable 区域和检索的延伸。有了之前那道题的基础,我们知道这道题其实也是换汤不换药,还是要建立一个累计区域和的数组,然后根据边界值的加减法来快速求出给定区域之和。这里我们维护一个二维数组dp,其中dp[i][j]表示累计区间(0, 0)到(i, j)这个矩形区间所有的数字之和,那么此时如果我们想要快速求出(r1, c1)到(r2, c2)的矩形区间时,只需dp[r2][c2] - dp[r2][c1 - 1] - dp[r1 - 1][c2] + dp[r1 - 1][c1 - 1]即可,下面的代码中我们由于用了辅助列和辅助行,所以下标会有些变化,参见代码如下:

class NumMatrix {
public:
    NumMatrix(vector<vector<int> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        dp.resize(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        for (int i = 1; i <= matrix.size(); ++i) {
            for (int j = 1; j <= matrix[0].size(); ++j) {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
    
private:
    vector<vector<int> > dp;
};

本文转自博客园Grandyang的博客,原文链接:二维区域和检索 - 不可变[LeetCode] Range Sum Query 2D - Immutable ,如需转载请自行联系原博主。

相关文章
|
6月前
|
算法
力扣240 搜索二维矩阵II
力扣240 搜索二维矩阵II
|
6月前
|
Go
golang力扣leetcode 240.搜索二维矩阵II
golang力扣leetcode 240.搜索二维矩阵II
37 0
|
5月前
|
机器学习/深度学习 算法 数据挖掘
LeetCode题目74:搜索二维矩阵
LeetCode题目74:搜索二维矩阵
|
6月前
|
算法
【Leetcode 74】搜索二维矩阵 —— 二分查找|矩阵
给你一个满足下述两条属性的`m x n`整数矩阵:每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数
|
6月前
|
索引 Python
leetcode-307:区域和检索 - 数组可修改
leetcode-307:区域和检索 - 数组可修改
34 0
|
6月前
|
JavaScript SoC
leetcode-304:二维区域和检索 - 矩阵不可变
leetcode-304:二维区域和检索 - 矩阵不可变
55 0
|
6月前
|
索引 Python
leetcode-303:区域和检索 - 数组不可变
leetcode-303:区域和检索 - 数组不可变
29 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2