本文主要是介绍304二维区域和检索 - 矩阵不可变，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
说明:
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法。
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
2、示例
给定 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
3、题解
基本思想：新建一个矩阵sum，sum[i][j]存储matrix中从(0,0)到(i,j)的元素的总和。计算(row1, col1)到(row2, col2)区域的元素和就等于sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1] 。
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
class NumMatrix {
public:NumMatrix(vector<vector<int>>& matrix) {//基本思想：新建一个矩阵sum，sum[i][j]存储matrix中从(0,0)到(i,j)的元素的总和//计算(row1, col1)到(row2, col2)区域的元素和就等于sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1] if (matrix.size() == 0) return;sum.resize(matrix.size(), vector<int>(matrix[0].size()));sum[0][0] = matrix[0][0];for (int i = 0; i < matrix.size(); i++){for (int j = 0; j < matrix[i].size(); j++){if (i == 0 && j == 0) continue;if (i == 0)sum[i][j] = sum[i][j - 1] + matrix[i][j];else if (j == 0)sum[i][j] = sum[i - 1][j] + matrix[i][j];elsesum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i][j];}}}int sumRegion(int row1, int col1, int row2, int col2) {if (row1 == 0 && col1 == 0)return sum[row2][col2];else if (row1 == 0)return sum[row2][col2] - sum[row2][col1 - 1];else if (col1 == 0)return sum[row2][col2] - sum[row1 - 1][col2];elsereturn sum[row2][col2] + sum[row1-1][col1-1] - sum[row2][col1-1] - sum[row1-1][col2];}
private:vector<vector<int>> sum;
};
int main()
{vector<vector<int>> 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}};NumMatrix* obj = new NumMatrix(matrix);int row1 = 0, col1 = 2, row2 = 4, col2 = 3;cout << obj->sumRegion(row1, col1, row2, col2) << endl;
}
这篇关于304二维区域和检索 - 矩阵不可变的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
