浙江备案需要开启网站吗,大埔县住房和城乡规划建设局网站,浙江网站建设推广公司找哪家,免费国外建站目录 【力扣】304. 二维区域和检索 - 矩阵不可变二维前缀和理论初始化计算面积 题解 【力扣】304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix#xff0c;以下类型的多个请求#xff1a;
计算其子矩形范围内元素的总和#xff0c;该子矩阵的 左上角 为 (row1, … 目录 【力扣】304. 二维区域和检索 - 矩阵不可变二维前缀和理论初始化计算面积 题解 【力扣】304. 二维区域和检索 - 矩阵不可变
给定一个二维矩阵 matrix以下类型的多个请求
计算其子矩形范围内元素的总和该子矩阵的 左上角 为 (row1, col1) 右下角 为 (row2, col2) 。
实现 NumMatrix 类
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。 提示 m matrix.length n matrix[i].length 1 m, n 200 - 1 0 5 10^5 105 matrix[i][j] 1 0 5 10^5 105 0 row1 row2 m 0 col1 col2 n 最多调用 1 0 4 10^4 104 次 sumRegion 方法
二维前缀和理论
初始化 因此二维前缀和预处理公式
s[i][j] s[i-1][j] s[i][j-1] -s[i-1][j-1] a[i][j]计算面积 因此二维前缀和计算公式以x1,y1为左上角x2,y2为右下角的子矩阵的和
s[x2][y2] - s[x2][y1 - 1] s[x1 - 1][y2] -s[x1 - 1][y1 - 1]题解
都加一数组从0,0开始
class NumMatrix {int[][] s;public NumMatrix(int[][] matrix) {int m matrix.length;if (m 0) {int n matrix[0].length;s new int[m 1][n 1];// 初始化for (int i 0; i m; i) {for (int j 0; j n; j) {s[i 1][j 1] s[i][j 1] s[i 1][j] - s[i][j] matrix[i][j];}}}}// 计算面积public int sumRegion(int x1, int y1, int x2, int y2) {return s[x2 1][y2 1] - s[x2 1][y1] - s[x1][y2 1] s[x1][y1];}
}
