个人主页：C++忠实粉丝
欢迎 点赞???? 收藏✨ 留言✉ 加关注????本文由 C++忠实粉丝 原创前缀和(8)_矩阵区域和
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论????
目录
温馨提示:
1. 题目链接 :
2. 题目描述 :
3. 解法(二维前缀和) :
题目解释:
算法思路 :
二位前缀和模板快速记忆:
1. 求二维前缀和
2. 使用二维前缀和
细节处理:
代码展示 :
结果分析 :
温馨提示:
本题需要使用二维前缀和模板,如果大家还不知道的话,可以查看下篇博客:
前缀和(2)_【模板】二维前缀和_模板-****博客
1. 题目链接 :
OJ链接: 矩阵区域和
2. 题目描述 :
给你一个 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
3. 解法(二维前缀和) :
题目解释:
就是目标点向四周延申k个,然后求出在合法区间的总和
算法思路 :
二维前缀和的简单应用题,关键就是我们在填写结果矩阵的时候,要找到原矩阵对应区域的[左上角]以及[右下角]的坐标(推荐大家画图)
左上角坐标: x1 = i - k, y1 = j - k, 但是由于会[超过矩阵]的范围,因此需要对0取一个max.因此修正后的坐标为: x2 = min(m - 1, i + k) y2 = min(n - 1, j + k)
然后将求出出来的坐标带入到[二位前缀和矩阵]的计算公式上即可~(但是要注意下标的映射关系,放到下面分析)
二位前缀和模板快速记忆:
1. 求二维前缀和
首先划出草图,我们这里的思路是:
将当前整个面积分成dp[x - 1][y] + dp[x][y - 1] + nums[x][y]
因为dp[x - 1][y - 1]多加了一次,我们需要在减去一次dp[x - 1][y - 1]
公式为 : dp[x][y] = dp[x - 1][y] + dp[x][y - 1] + nums[x][y] - dp[x - 1][y - 1]
2. 使用二维前缀和
首先划出草图,我们这里的思路是:
将当前整个面积分成dp[x1 - 1][y1 - 1] dp[x2][y1 - 1] dp[x1 - 1][y2]
公式为 : ret = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 -1] + dp[x1 -1][y1 - 1]
细节处理:
下标的映射关系:
因为题目原数组从0开始,我们的二维前缀和数组需要访问-1的位置,这样就会导致访问未知内存程序崩溃,所以我们可以将第0行第0列不填数,规避这道题的边界问题.
代码展示 :
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] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
//使用前缀和
vector<vector<int>> ret(n, vector<int> (m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
int x2 = min(n - 1, i + k) + 1, y2 = min(m - 1, j + k) + 1;
ret[i][j] = dp[x2][y2] - dp[x1- 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
return ret;
}
};代码分析:
前缀和计算：
使用 dp 数组来存储 mat 的前缀和。dp[i][j] 表示从 mat[0][0] 到 mat[i - 1][j - 1] 的所有元素的和。
前缀和的公式为：
dp[i][j] = dp[i−1][j] + dp[i][j−1] + mat[i−1][j−1]−dp[i−1][j−1]
这样，dp 数组的每个元素能够快速计算出任意子矩阵的和。
块和计算：
使用前缀和 dp 来计算每个元素的块和：
计算块的边界：
左上角(x1, y1) 为(max(0, i - k) + 1, max(0, j - k) + 1)
右下角(x2, y2) 为(min(n - 1, i + k) + 1, min(m - 1, j + k) + 1)
利用前缀和公式来计算块和：
块和 = dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1] + dp[x1−1][y1−1]
结果存储：
将每个块的和存储在 ret 数组中，并最终返回。
结果分析 :
时间复杂度
前缀和的计算时间复杂度为O(n×m)，因为需要遍历整个矩阵一次。
计算每个元素的块和的时间复杂度也是O(n×m)，同样是遍历整个矩阵一次。
因此，总的时间复杂度为：O(n×m)
空间复杂度
dp 数组的大小为(n + 1)×(m + 1)，因此空间复杂度为O(n×m)。
ret 数组的大小为n×m，也为O(n×m)。
因此，总的空间复杂度也是：O(n×m)