本文主要是介绍Range Sum Query 2D - Immutable,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这道题一定要注意下标,一开始自己做的全都没有下标-1这一操作。
public class NumMatrix {int[][] sum;public NumMatrix(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return;}int row = matrix.length;int col = matrix[0].length;sum = new int[row][col];for (int i = 0; i < row; i++) {if (i == 0) {sum[i][0] = matrix[0][0];} else {sum[i][0] = matrix[i][0] + sum[i - 1][0];}}for (int i = 1; i < col; i++) {sum[0][i] = matrix[0][i] + sum[0][i - 1];}for (int i = 1; i < row; i++) {for (int j = 1; j < col; j++) {sum[i][j] = matrix[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {if (sum == null) {return 0;}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[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1];}}
}// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);
这篇关于Range Sum Query 2D - Immutable的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!