每日一练：前缀和-矩阵区域和

1314. 矩阵区域和 - 力扣（LeetCode）

题目要求：

给你一个 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

前缀和 O(N^2)：

        题目的意思就是求以每个位置为中心，2*k+1为边长的正方形中的所有元素和。

        该题是二维前缀和，假设需要求某个范围t的和：

        设dp[i][j]是左上角为(0,0)，右下角为(i,j)的矩形的值，那么红色区域的面积就是dp[i+k][j+k]-dp[i+k][j-k-1]-dp[i-k-1][j+k]+dp[i-k-1][j-k-1]。

        所以先创建一个dp数组，记录左上角为(0,0)，右下角为(i,j)的矩形的值，然后按顺序进行填写answer即可。

        细节：

        正方形的左上角或者右下角可能越界，所以一但越界就取边界值。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));

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


        vector<vector<int>> answer(n,vector<int>(m));
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++){
                // 因为dp是从下标1开始的，所以赋值时需要加1
                int bottom=i+1+k,right=j+1+k;
                bottom=min(bottom,n);
                right=min(right,m);

                int top=i+1-k,left=j+1-k;
                top=max(top,1);
                left=max(left,1);

                answer[i][j]=dp[bottom][right]+dp[top-1][left-1]-
                             dp[bottom][left-1]-dp[top-1][right];
            }
        return answer;
    }
};

原文地址：https://blog.csdn.net/2303_78095330/article/details/143892427

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！