Range Sum Query 2D - Immutable
思路:
思想和303差不多。变为一个2D的表格。每个格子是从(0,0)到(i,j)矩形内所有格子之和。动态规划,每次计算和的时候用上几次计算的结果。时间复杂度为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也很占时间啊。。按照303改动不行
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
大神代码就是简洁
空间复杂度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);
*/
网友评论