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).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
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) -> 12Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
给定一个矩阵，要求矩阵中的任意一个子矩阵的和，而且可能有很多次这样的请求。 因为之前在hiho上做过一个用DP求子矩阵的和的题，所以这题就很easy了。 定义一个二维数组dp[i][j]表示固定子矩阵的左上角坐标为(1,1)（假设矩阵的下标从1开始），当右下角坐标为(i,j)时，这个子矩阵的和是多少。则有： dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+matrix[i][j] 这个很好理解，相当于求面积，dp[i][j-1]+dp[i-1][j]加了两遍dp[i-1][j-1]，所以要减掉一个，最后再加上dp[i][j]独有的matrix[i][j]。 有了dp[i][j]之后，怎样求任意一个子矩阵的和呢？假设我们要求第i,j两行、u,v两列交成的子矩阵的和，应该怎样计算呢。这个也很好算，也是面积的加加减减，如下图所示，把(j,v)的面积减去(j,u)左边以及(i,v)上边的面积，但是(i,u)左上的面积减了两次，所以还要加上。总结成公式就是： cursum=dp[j][v]-dp[j][u-1]-dp[i-1][v]+dp[i-1][u-1]
| |
-----(i,u)----------(i,v)----
| |
| |
-----(j,u)----------(j,v)----
| |
通过cursum公式，我们很容易就能求出任意一个子矩阵的和了。代码如下：
[cpp]
class NumMatrix {
private:
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>> matrix) {
if (matrix.empty() || matrix[0].empty())return;
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m + 1; ++i)dp.push_back(vector<int>(n + 1, 0)); // 为了方便，多增加了一行和一列
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++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) {
if (dp.empty())return 0;
++row1; // 因为dp多一行和一列，所以这里提前加上
++col1;
++row2;
++col2;
return dp[row2][col2] – dp[row2][col1 – 1] – dp[row1 – 1][col2] + dp[row1 – 1][col1 – 1];
}
};
[/cpp]
本代码提交AC，用时22MS。]]>