调查问卷网站建设,湖南好搜网站建设,ktv网站模板,厦门市建设管理协会网站首页1314. 矩阵区域和 - 力扣#xff08;LeetCode#xff09; 给你一个 m x n 的矩阵 mat 和一个整数 k #xff0c;请你返回一个矩阵 answer #xff0c;其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和#xff1a;
i - k r i k, j - k c …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]]
题意就是要计算 假设给出的 mat[i][j] 那么就要是要计算下图当中给出的 区域的全部元素之和 新返回的矩形当中应该存储的是上述 绿色区域当中的全部的 元素之和。k 1 所以我们可以利用二位矩阵的前缀和 来解决上述的问题。
对于 前缀和 二位矩阵 的计算可以参考之前博客
leedcode 刷题 - 除自身以外数组的乘积 - 和为 K 的子数组-CSDN博客
leetcode - 串联所有单词的子串 - 最小覆盖子串 - x 的平方根-CSDN博客 上述就是递归公式但是 dp[x2][y2] 不是在 dp 这个 二维前缀和数组当中的这个位置是没有 数据的所以其实这个位置的数据是在 mat 当中的。也就对应的是 mat[i][j] 。
所以上述就计算出了存储前缀和的二维数组。
此时我们只需要根据上述的 存储前缀和的二维数组就可以像下图当中这样去 计算某一个满足题意的 区间的 元素之和 即
ret dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] dp[x1 - 1][y1 - 1] 上述就是递推公式。 在上述计算出递推公式之后就可以开始计算上述的 x1 y1 和 x2 y2 了。 上述前缀和二维数组当中的 下标是从 (1, 1) 开始计数的但是在题目当中的二维数组是从 (0,0) 开始计数的所以为了方便上述 前缀和二维数组的计算所以我们直接把 dp 数组加一行加一列 使用黑色位置存储元素值。 dp[x][y] - mat[x - 1][y -1]dp[x][y] - ans[x - 1][y -1]
所以此时应该是 完整代码
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();//计算出前缀和二维数组vectorvectorint dp(m 1, vectorint(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] - dp[i - 1][j - 1] mat[i - 1][j - 1];// 计算出 answer 二维数组的值vectorvectorint ret(m, vectorint(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;int x2 min(m - 1 , i k) 1, y2 min(n - 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;}
};
