LeetCode 304. Range Sum Query 2D - Immutable

Problem

LeetCode 304. Range Sum Query 2D - Immutable

1. 题目简述

给出一个二维矩阵，矩阵中每个元素都是整数。然后给出一个左上角和右下角（保证合法），计算给出的围起来的长方形的值。例如：

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:

1. sumRegion函数会被call很多次；

2. 假设矩阵不变；

2. 算法思路

相关问题：

1. LeetCode 308. Range Sum Query 2D - Mutable（未做——线段树）
2. LeetCode 303. Range Sum Query - Immutable

这道题比起dp问题更像是一个数学问题。

DP(Math方法)

其实有点像求面积，用图来画一下会比较直白。我们目标就是绿色部分的面积（或者说是数字和），根据(row1, col1)和(row2, col2)我们可以清楚地知道四个部分的面积，相信一眼就能看出来这里怎么算了，我们用S(row, col)来表示从(0, 0)点到(row, col)的面积大小:

$$Target = S(row2, col2) - S(row1, col2) - S(row2, col1) + S(row1, col1)$$

时间复杂度：O(m * n)，初始化时候的复杂度，其他操作为O(1)。

另外，下面的写法欧典复杂了，判断了很多边界情况，其实可以做padding的，第二种写法是solution里做了padding的写法，更加简洁，可以参考一下。

class NumMatrix {

    int[][] dp;
    int m = 0, n = 0;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        m = matrix.length;
        n = matrix[0].length;

        dp = new int[m][n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += matrix[0][i];
            dp[0][i] = sum;
        }

        for (int i = 1; i < m; i++) {
            sum = 0;
            for (int j = 0; j < n; j++) {
                sum += matrix[i][j];
                dp[i][j] = sum + dp[i - 1][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = dp[row2][col2];
        // sum1是左上角，sum2是上方，sum3是左侧。
        if (row1 == 0 && col1 == 0) {
            sum1 = 0;
            sum2 = 0;
            sum3 = 0;
        } else if (row1 == 0 && col1 != 0) {
            sum1 = 0;
            sum2 = 0;
            sum3 = dp[row2][col1 - 1];
        } else if (row1 != 0 && col1 == 0 ) {
            sum1 = 0;
            sum2 = dp[row1 - 1][col2];
            sum3 = 0;
        } else {
            sum1 = dp[row1 - 1][col1 - 1];
            sum2 = dp[row1 - 1][col2];
            sum3 = dp[row2][col1 - 1];
        }

        return sum4 - sum2 - sum3 + sum1;
    }
}

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

DP（做padding，简单写法）

class NumMatrix {
    private int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}