6ms Java DP solution


  • 0
    L
    public class NumMatrix {
    /**
     * sum[i][j] = sum from(0,0) to (i,j)
     * construct sum[][] in constructor:
     * sum[row2][0] = sum[row2-1][0]+matrix(row2,0)
     * sum[0][col2] = sum[0][col2-1]+matrix(0,col2)
     * sum[row2][col2] = sum[row2][col2-1]+ sum[row2-1][col2]-sum[row2-1][col2-1]+maxtrix[row2][col2]
     * calculate sumRegion in sumRegion():
     * if r1 = 0, sumRegion = sum(r2,c2)-sum(r2,c1-1)
     * if c1 = 0, sumRegion = sum(r2,c2)-sum(r1-1,c2)
     * sumRegion(r1,c1,r2,c2)= sum(r2,c2)-sum(r1-1,c2)-sum(r2,c1-1)+sum(r1-1,c1-1)
     * */
    private int[][] sum;
    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        if(row == 0) return;
        int col = matrix[0].length;
        sum = new int[row][col];
        sum[0][0] = matrix[0][0];
        for(int i=1;i<row;i++) sum[i][0] = sum[i-1][0]+matrix[i][0];
        for(int j=1;j<col;j++) sum[0][j] = sum[0][j-1]+matrix[0][j];
        for(int i=1;i<row;i++){
            for(int j = 1;j<col;j++){
                sum[i][j] = sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1==0&&col1==0) return sum[row2][col2];
        else if(row1==0) return sum[row2][col2]-sum[row2][col1-1];
        else if(col1==0) return sum[row2][col2]-sum[row1-1][col2];
        else return sum[row2][col2]-sum[row1-1][col2]-sum[row2][col1-1]+sum[row1-1][col1-1];
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.