LeetCode 304. 二维区域和检索 - 矩阵不可变

梦里梦外; 2022-11-06 01:52 108阅读 0赞

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例：
    
    给定 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
     
    
    提示：
    
    你可以假设矩阵不可变。
    会多次调用 sumRegion 方法。
    你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：计算每一行的数值和，再根据子矩阵可能出现的类型进行分类讨论即可

class NumMatrix {
        
        int sum[][];
        int row;
        int col;
    	public NumMatrix(int[][] matrix) {
        
    		row=matrix.length; 
    		if(row>0) col=matrix[0].length;
    		if(col>0) {
        
    			sum=new int[row][col];
    			for(int i=0;i<row;i++) sum[i][0]=matrix[i][0];
    			for(int i=0;i<row;i++) {
        //计算每一行的和
    				for(int j=1;j<col;j++) {
        
    					sum[i][j]=sum[i][j-1]+matrix[i][j];
    				}
    			}
    		}
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
        
        	int res=0;
        	if(row1==0&&col1==0) {
        
        		for(int i=row1;i<=row2;i++) res+=sum[i][col2];
        	}
        	else if(row1==0) {
        
        		for(int i=row1;i<=row2;i++) {
        
        			res+=sum[i][col2]-sum[i][col1-1];
        		}
        	}
        	else if(col1==0) {
        
        		for(int i=row1;i<=row2;i++) res+=sum[i][col2];
        	}
        	else {
        
        		for(int i=row1;i<=row2;i++) {
        
        			res+=sum[i][col2]-sum[i][col1-1];
        		}
        	}
        	return res;
        }
    }
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * int param_1 = obj.sumRegion(row1,col1,row2,col2);
     */