Range Sum Query 2D - Immutable

思路:
思想和303差不多。變?yōu)橐粋€(gè)2D的表格。每個(gè)格子是從（0，0）到（i，j）矩形內(nèi)所有格子之和。動(dòng)態(tài)規(guī)劃，每次計(jì)算和的時(shí)候用上幾次計(jì)算的結(jié)果。時(shí)間復(fù)雜度為O(n)。

Runtime Error

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {
        if( matrix.length == 0) return;
        if(matrix[0].length == 0) return;
        int height = matrix.length;
        int width = matrix[0].length;
        sums = new int[height][width];
        sums[0][0] = matrix[0][0];
        for(int j = 1; j< width; j++){
            sums[0][j] = matrix[0][j] + sums[0][j-1];
        }
        for(int i = 1; i< height; i++){
            sums[i][0] = matrix[i][0] + sums[i-1][0];
        }
        for(int i = 1; i< height; i++){
            for (int j = 1; j< width; j++){
                sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int temp = 0;
        if(row1 >= 1){
            if(col1 >= 1){
                temp = sums[row2][col2] - sums[row2][col1-1] - sums[row1-1][col2] + sums[row1-1][col1-1];
            }else{
                temp = sums[row2][col2] - sums[row1-1][col2];
            }
            
        }else{
            temp =  sums[row2][col2] - sums[row2][col1-1];
        }
        return temp;

    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

看來查詢nums也很占時(shí)間啊。。按照303改動(dòng)不行

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {
        if( matrix.length == 0) return;
        if(matrix[0].length == 0) return;
        int height = matrix.length;
        int width = matrix[0].length;
        sums =  matrix.clone();
        for(int j = 1; j< width; j++){
            sums[0][j] += sums[0][j-1];
        }
        for(int i = 1; i< height; i++){
            sums[i][0] += sums[i-1][0];
        }
        for(int i = 1; i< height; i++){
            for (int j = 1; j< width; j++){
                sums[i][j] += sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int temp = 0;
        if(row1 >= 1){
            if(col1 >= 1){
                temp = sums[row2][col2] - sums[row2][col1-1] - sums[row1-1][col2] + sums[row1-1][col1-1];
            }else{
                temp = sums[row2][col2] - sums[row1-1][col2];
            }
            
        }else{
            temp =  sums[row2][col2] - sums[row2][col1-1];
        }
        return temp;

    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

看了solution
大神代碼就是簡潔
空間復(fù)雜度O（1）
AC了終于

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {
        if( matrix.length == 0) return;
        if(matrix[0].length == 0) return;
        int height = matrix.length;
        int width = matrix[0].length;
        sums =  new int[height + 1][width +1];

        for(int i = 1; i< height+1; i++){
            for (int j = 1; j< width+1; j++){
                sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
            
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */