dp第14天

1314. 矩阵区域和

这题的基础是前缀和，后面估计也会做到，这题的边界比较难控制，值的多看几遍。

前缀和，就是（0，0）到(i,j)这里的元素的和，k代表（i,j）四周举例为k的正方形，输出区域的和，公式 dp[i][j] = mat[i][j] + dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1];i,j从1开始，因为外层补了一层0

感谢这个大兄弟的图 https://leetcode-cn.com/problems/matrix-block-sum/solution/lei-qian-zhui-he-dong-tai-gui-hua-hua-tu-53z6/

/**
 1314. 矩阵区域和
 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

 i - k <= r <= i + k,
 j - k <= c <= j + k 且
 (r, c) 在矩阵内。


 示例 1：

 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
 输出：[[12,21,16],[27,45,33],[24,39,28]]
 示例 2：

 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
 输出：[[45,45,45],[45,45,45],[45,45,45]]


 提示：

 m == mat.length
 n == mat[i].length
 1 <= m, n, k <= 100
 1 <= mat[i][j] <= 100

 * @author zeroheart
 *
 */
public class Question1314 {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        // 这题单独看题目，一开始是完全不知所云的。看了一些图解才知道要做的事情。
        // 1.前缀和，就是（0，0）到(i,j)这里的元素的和，k代表（i,j）四周举例为k的正方形，输出区域的和。
        // 感谢这个大兄弟的图 https://leetcode-cn.com/problems/matrix-block-sum/solution/lei-qian-zhui-he-dong-tai-gui-hua-hua-tu-53z6/
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[m+1][n+1]; // 在左边和上面加了一排0，dp[1][1]实际就是dp[0][0]

        int[][] res = new int[m][n]; // 在左边和上面加了一排0，dp[1][1]实际就是dp[0][0]

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

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int x = Math.max(i-k, 0);
                int x1 = Math.min(i+k, m-1);
                int y = Math.max(j-k, 0);
                int y1 = Math.min(j+k, n-1);

                res[i][j] = dp[x1+1][y1+1] - dp[x1+1][y] - dp[x][y1+1] + dp[x][y];
            }
        }
        return res;

    }

    public static void main(String[] args) {
    }
}

304. 二维区域和检索 – 矩阵不可变

这一题直接巩固了上面的结论，直接用前缀和+面积内和的做法就行，在写一下公式

1.前缀和：dp[i][j] = mat[i][j] + dp[i-1][j] + dp[i][j-1] – dp[i-1][j-1];i,j从1开始，因为外层补了一层0

2.面积内和res[i][j] = dp[x1+1][y1+1] – dp[x1+1][y] – dp[x][y1+1] + dp[x][y];x1<=m-1;y1<=n-1;

/**
 304. 二维区域和检索 - 矩阵不可变
 给定一个二维矩阵 matrix，以下类型的多个请求：

 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
 实现 NumMatrix 类：

 NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。


 示例 1：



 输入:
 ["NumMatrix","sumRegion","sumRegion","sumRegion"]
 [[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
 输出:
 [null, 8, 11, 12]

 解释:
 NumMatrix numMatrix = new NumMatrix([[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]]);
 numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
 numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
 numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)


 提示：

 m == matrix.length
 n == matrix[i].length
 1 <= m, n <= 200
 -105 <= matrix[i][j] <= 105
 0 <= row1 <= row2 < m
 0 <= col1 <= col2 < n
 最多调用 104 次 sumRegion 方法

 * @author zeroheart
 *
 */
public class Question304 {
    int[][] dp;
    public void NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m+1][n+1];

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

    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];
    }

    public static void main(String[] args) {
    }
}