leetcode 304. Range Sum Query 2D - Immutable 子矩阵求和 + DP

秒速五厘米 2022-06-06 23:06 163阅读 0赞

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).

![这里写图片描述][SouthEast]

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.

题意很简单，做法也很简单，把上一道题[leetcode 303. Range Sum Query - Immutable 字串求和 + DP][leetcode 303. Range Sum Query - Immutable _ _ DP] 做一下扩展即可。

代码如下：

/*
     * 就是面积的迭代计算
     * DP的一个简单应用
     * */
    class NumMatrix 
    {
        
        public int[][] sum=null;
        public NumMatrix(int[][] matrix)
        {
            if(matrix==null || matrix.length<=0)
                return ;
            sum=new int[matrix.length][matrix[0].length];
    
            sum[0][0]=matrix[0][0];
            for(int i=1;i<matrix.length;i++)
                sum[i][0]=sum[i-1][0]+matrix[i][0];
            for(int i=1;i<matrix[0].length;i++)
                sum[0][i]=sum[0][i-1]+matrix[0][i];
    
            for(int i=1;i<matrix.length;i++)
            {
                for(int j=1;j<matrix[0].length;j++)
                {
                    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i][j];
                }
            }
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) 
        {
            if(sum==null || sum.length<=0 || row1<0 || col1>=sum[0].length
            || row2<0 || col2>=sum[0].length)
                return 0;
    
            if(row1>row2 || col1 > col2)
                return 0;
            else if(row1==0 && col1==0)
                return sum[row2][col2];
            else if(row1==0 && col1!=0)
                return sum[row2][col2]-sum[row2][col1-1];
            else  if(row1!=0 && col1==0)
                return sum[row2][col2]-sum[row1-1][col2];
            else 
                return sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1];
        }
    }
    
    /**
     * Your NumMatrix object will be instantiated and called as such:
     * NumMatrix obj = new NumMatrix(matrix);
     * int param_1 = obj.sumRegion(row1,col1,row2,col2);
     */

[SouthEast]: /images/20220607/dbafeab0cb95411ca0c549032a34d6f2.png
[leetcode 303. Range Sum Query - Immutable _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78131390