当前位置：首页 > news >正文

LeetCode -- Range Sum Query 2D - Immutable

news 来源：原创 2024/5/20 15:46:58

题目描述：

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given 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
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

给定一个矩阵，传入(x1,y1) (x2,y2)，返回两坐标构成的矩形中包含的数字之和。

思路：
在初始化矩阵时，缓存每个坐标到原点构成的面积（数字之和）。这样多次调用对性能的影响是幂等的。
面积计算时，找出坐标面积之间的关系进行计算即可：设左上坐标为 p0(0,0) ，坐标1 p1(x1,y1)，坐标2 p2(x2, y2)，并假设p2在p1的右下方（横纵坐标大于等于）。
S = S[x2,y2](总面积) - S[x1-1,y2]（x1左侧面积） - S[x2, y1-1]（y1上面面积） + S(x1-1,y1-1)（多减去的部分）

实现代码：

public class NumMatrix {
        private int[,] _matrix;
        private int[,] _sum;
        public NumMatrix(int[,] matrix) {
            _matrix = matrix;
    		CreateCache();
        }
    
        public int SumRegion(int row1, int col1, int row2, int col2) {
    		// get the all
    		var areaTotal = _sum[row2, col2]; 
    		
    		// remove the left side sum
    		var areaLeft = col1 > 0 ? _sum[row2, col1-1] : 0;
    		// remove the top side sum
    		var areaTop = row1 > 0 ? _sum[row1-1, col2] : 0;
    		
    		var result = areaTotal - areaLeft - areaTop;
    		// check if there is overlay between top area and left area
    		if(row1 > 0 && col1 > 0){
    			var common = _sum[row1-1,col1-1];
    			result += common;
    		}
    		return result;
        }
    	
    	private void CreateCache(){
    		var rows = _matrix.GetLength(0);
    		var columns = _matrix.GetLength(1);
    		if(rows == 0 && columns == 0){
    			return ;
    		}
    		
    		
    		_sum = new int[rows,columns];
    		
    		// init the first row and column value
    		_sum[0,0] = _matrix[0,0];
    		for (var i = 1;i < rows;i ++){
    			_sum[i,0] = _matrix[i,0] + _sum[i-1,0];
    		}
    		for (var j = 1;j < columns; j++){
    			_sum[0,j] = _matrix[0,j] + _sum[0, j-1];
    		}
    		
    		// from top to bottom , left to right
    		// cache the sum value of each rect
    		for (var i = 1;i < rows; i++){
    			for (var j = 1;j < columns; j++){
    				_sum[i,j] = _matrix[i,j]+ _sum[i,j-1] + _sum[i-1, j] - _sum[i-1,j-1];
    			}
    		}
    		
    	//	Console.WriteLine(_sum);
    	}
}




// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.SumRegion(0, 1, 2, 3);
// numMatrix.SumRegion(1, 2, 3, 4);