【算法|前缀和系列No.5】leetcode1314. 矩阵区域和

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【Leetcode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

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

2️⃣题目解析

• answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]

其中：

• x1 = max(0,i - k) + 1、y1 = max(0,j - k) + 1、x2 = min(i + k,m - 1) + 1、y2 = min(j + k,n - 1) + 1

另外一定要注意下标的映射关系。

3️⃣解题代码

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        // 创建前缀和矩阵
        vector<vector<int>> dp(m + 1,vector<int>(n + 1));
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];

        // 使用前缀和矩阵
        vector<vector<int>> answer(m,vector<int>(n));
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++)
            {
            	// 注意下标的映射关系
                int x1 = max(0,i - k) + 1,y1 = max(0,j - k) + 1,x2 = min(i + k,m - 1) + 1,y2 = min(j + k,n - 1) + 1;
                answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        return answer;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后就通过啦！！！