网站用户体验设计,中国互联网协会什么级别,网站建设视频教程免费下载,江西省赣州市教育局LCR 013. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix#xff0c;以下类型的多个请求#xff1a;
计算其子矩形范围内元素的总和#xff0c;该子矩阵的左上角为 (row1, col1) #xff0c;右下角为 (row2, col2) 。
实现 NumMatrix 类#xff1a;
NumMatrix(…LCR 013. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix以下类型的多个请求
计算其子矩形范围内元素的总和该子矩阵的左上角为 (row1, col1) 右下角为 (row2, col2) 。
实现 NumMatrix 类
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。
示例 1
输入:
[NumMatrix,sumRegion,sumRegion,sumRegion]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]解释:
NumMatrix numMatrix new NumMatrix([[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.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)提示
m matrix.lengthn matrix[i].length1 m, n 200-105 matrix[i][j] 1050 row1 row2 m0 col1 col2 n最多调用 104 次 sumRegion 方法
法1暴力
**分析**两层for循环遍历
时间复杂度 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( 1 ) O(1) O(1) var NumMatrix function(matrix) {this.matrix matrix;
};NumMatrix.prototype.sumRegion function(row1, col1, row2, col2) {matrix this.matrix;let result 0;for (let r row1; r row2; r) {for (let c col1; c col2; c) {result matrix[r][c];}}return result
};const 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]
];
var obj new NumMatrix(matrix);
console.log(obj.sumRegion(2, 1, 4, 3)); // 输出 8
console.log(obj.sumRegion(1, 1, 2, 2)); // 输出 11
console.log(obj.sumRegion(1, 2, 2, 4)); // 输出 12leetcode上通过不了
法2 前缀和Prefix Sum
分析
定义一个prefixSum 比原本的matrix多一行多一列。
在 prefixSum 中prefixSum[i][j] 表示从 (0,0) 到 (i-1, j-1) 的区域和。
比如要计算prefixSum[3][3]也就是matrix[3][3]左上角的和。 28怎么来要求matrix[3][3]左上角的和也就是要求
28 matrix[i - 1][j - 1] //这个就是matrix[2][2]1this.prefixSum[i - 1][j] //prefixSum[2][3]matrix[2][3]左上角的和16this.prefixSum[i][j - 1] //prefixSum[3][2]matrix[3][2]左上角的和22
- this.prefixSum[i - 1][j - 1];//prefixSum[2][2]matrix[2][2]左上角的和11
// 11622-1128可以看出prefixSum[3][2]和prefixSum[2][3]有交集prefixSum[2][2],多以最后要减去一个prefixSum[2][2]再加上maxtrix[2][2](图中绿色填充)的。
int sumRegion(int row1, int col1, int row2, int col2)
再看比如说计算sumRegion(1,1,2,2)
this.prefixSum[row2 1][col2 1] - // prefixSum[3][3]
this.prefixSum[row1][col2 1] - // prefixSum[1][3]
this.prefixSum[row2 1][col1] // prefixSum[3][1]
this.prefixSum[row1][col1]; // prefixSum[1][1]时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( 1 ) O(1) O(1) var NumMatrix function(matrix) {// 初始化 NumMatrix 类的实例属性 matrixthis.matrix matrix;const m matrix.length;const n matrix[0].length;// 创建一个 m1 x n1 的前缀和数组 (多加一行一列是为了方便计算)this.prefixSum Array(m 1).fill().map(() Array(n 1).fill(0));// 填充前缀和数组for (let i 1; i m; i) {for (let j 1; j n; j) {this.prefixSum[i][j] matrix[i - 1][j - 1] this.prefixSum[i - 1][j] this.prefixSum[i][j - 1] - this.prefixSum[i - 1][j - 1];}}
};NumMatrix.prototype.sumRegion function(row1, col1, row2, col2) {// 使用前缀和公式计算区域和return this.prefixSum[row2 1][col2 1] - this.prefixSum[row1][col2 1] - this.prefixSum[row2 1][col1] this.prefixSum[row1][col1];
};
