LeetCode(304)Range Sum Query 2D - Immutable
2024-08-23 01:53:54
题目
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:
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.
分析
思想与上一题相同。
注意下标处理方式。
AC代码
class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
if (matrix.empty())
return;
//求得二维矩阵的行列
int m = matrix.size(), n = matrix[0].size();
sums = vector<vector<int>>(m+1, vector<int>(n+1, 0));
sums[0][0] = matrix[0][0];
for (int j = 1; j <= n; ++j)
{
sums[0][j] = 0;
}
for (int i = 1; i <= m; ++i)
{
sums[i][0] = 0;
}
//
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{
sums[i][j] = sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1] + matrix[i-1][j-1];
}//for
}//for
}
int sumRegion(int row1, int col1, int row2, int col2) {
//求得二维矩阵的行列
int m = sums.size(), n = sums[0].size();
if (row1 < 0 || row1 >= m || col1 < 0 || col1 >= n || row2<0 || row2 >= m ||
col2<0 || col2 >= n || row1 >row2 || col1 > col2)
{
return 0;
}
return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
}
private:
vector<vector<int>> sums;
};
最新文章
- 企业app分发
- BZOJ2706 : [SDOI2012]棋盘覆盖
- 20160621-BAPI 更改外向DN&;更改拣配
- 基于HTML5的燃气3D培训仿真系统
- TYVJ P1020 寻找质因数
- 配置DNS
- CryptAPI 数字签名 与 Openssl 验证签名
- 数据结构【三】:简单优先队列PriorityQueue
- 优化 MySQL 中的分页
- LRU 缓冲池 (不考虑多线程)
- kswapd0、kjournald、pdflush、kblocked、migration进程含义 转
- 现在,以编程方式在 Electron 中上传文件,是非常简单的!
- centos 7.3二进制安装mariadb10.2.8完美步骤
- Python内置函数(65)——staticmethod
- MVC从Controller到View的呈现
- MachineLN博客目录
- mysql之整型数据int
- 进化树(phylogenetic trees)
- Win32 实现 MFC CFileDialog 对话框
- mysql部分学习心得(入门级别)