LeetCode刷题【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

理解题意

根据题意：所求新数组answer[row][col]的值就是原数组的mat[row][col]位置上下左右下标距离k这个这个区域内的所有数字之和

若距离k为1,则answer[3][3]的值为周围距离k的矩形区域内的所有数字之和。
那么顺着题意，想要求这片红色区域的所有数字只有的话，我们有两个方法

遍历这个区域内的所有格子，求和处理
这片红色区域的数字之和 = 蓝色区域的数字之和 - 黄色区域之和 - 紫色区域之和 + 黑色区域之和
黑色区域的和值之前重复减掉的那么顺着这个和数组的前缀和非常像的思路，我们要怎么求这某个格子的所有左上格子内的数字之和呢？

右下角为29的蓝色区域的所有数字之和 = 23格子代表的紫色区域的所有数字之和 + 28代表的黄色区域数字之和 - 22代表的黑色区域的所有数字之和 + 29这个格子内的值

因为遍历的顺序是从上往下，从左往右，在第29这个格子的时候，前面的22,23,28的格子内的值都是已知的。

那么思路就很清楚了

一些边界情况

1. 在求前缀和的时候，如果是第0行或者是每行的第一个格子，他们的上一行或者前一个格子是不存在的，直接取值0
2. 当在求第一个图中红色区域的时候，如果红色区域超出了原本的数组的边界，应当取原本数组边界的位置

代码

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] preSum = new int[mat.length][mat[0].length];
        for (int row = 0; row < preSum.length; row++) {
            for (int col = 0; col < preSum[row].length; col++) {
                preSum[row][col] = getMatrixNum( preSum, row-1, col)
                        + getMatrixNum( preSum, row, col-1)
                        - getMatrixNum( preSum, row-1, col-1)
                        + mat[row][col];
            }
        }

        int[][] answer = new int[mat.length][mat[0].length];
        for (int row = 0; row < answer.length; row++) {
            for (int col = 0; col < answer[row].length; col++) {
                answer[row][col] = getPreSumMatrixNum(preSum, row+k, col+k)
                        + getPreSumMatrixNum(preSum, row-k-1, col-k-1)
                        - getPreSumMatrixNum(preSum, row+k, col-k-1)
                        - getPreSumMatrixNum(preSum, row-k-1, col+k);
            }
        }
        return answer;
    }

    public int getMatrixNum(int[][] matrix, int row, int col){
        if (row < 0 || col < 0){
            return 0;
        }
        return matrix[row][col];
    }

    public int getPreSumMatrixNum(int[][] matrix, int row, int col){
        if (row < 0 || col < 0){
            return 0;
        }
        row = row > matrix.length-1 ? matrix.length-1 : row;
        col = col > matrix[row].length-1 ? matrix[row].length-1 : col;
        return matrix[row][col];
    }

}

本题和另外一题，LeetCode刷题【304】二维区域和检索 – 矩阵不可变基本一样，可以结合起来一起理解