怎么向百度提交网站,旅游景区网站模板,ui设计培训学校哪家好,html页面转WordPress文章304. 二维区域和检索 - 矩阵不可变
题目描述#xff1a; 给定一个二维矩阵 matrix#xff0c;以下类型的多个请求#xff1a;
计算其子矩形范围内元素的总和#xff0c;该子矩阵的 左上角 为 (row1, col1) #xff0c;右下角 为 (row2, col2) 。 实现 NumMatrix 类…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) 所描述的子矩阵的元素 总和 。
考察重点(前缀和、区域和检索) 先将0-i(0in)的和都存储于数组sum中即到第i位之和为sum[i]i 到 j 之和sum[j]-sum[i-1]二维数组同理。
func Constructor9(matrix [][]int) NumMatrix { //sumMatrix[i][j]保存从(0,0)到(i,j)的元素和for i : 0; i len(matrix); i {if i 0 { //(0,0) (0,0)matrix[i][0] matrix[i-1][len(matrix[0])-1] //换行之后(i,j)等于(i-1,len)(i,j)}for j : 1; j len(matrix[0]); j { //其他位置(i,j)等于(i-1,j)(i,j)matrix[i][j] matrix[i][j-1]}}return NumMatrix{sumMatrix: matrix}
}func (t *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {sum : 0for i : row1; i row2; i {//考虑左上角(0,0)到右下角(i,j)的情况 以及 左上角(i,0)到右下角(i,j)if col1 0 {if i 0 {sum t.sumMatrix[i][col2] //原点直接加continue} //(i,j)等于 (i,j)-(i-1,len)sum (t.sumMatrix[i][col2] - t.sumMatrix[i-1][len(t.sumMatrix[0])-1])continue}sum (t.sumMatrix[i][col2] - t.sumMatrix[i][col1-1])}return sum
}
