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);
新闻热点
疑难解答