2024每日刷题(137)
Leetcode—304. 二维区域和检索 - 矩阵不可变
算法思想
实现代码
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
prefix.resize(m + 1, vector<int>(n + 1));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
prefix[i + 1][j + 1] = prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return prefix[row2 + 1][col2 + 1] - prefix[row2 + 1][col1] - prefix[row1][col2 + 1] + prefix[row1][col1];
}
private:
vector<vector<int>> prefix;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
运行结果
之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!