商务网站业务流程,调研报告万能模板,wordpress注册页面主题,营销推广的平台文章目录 题目链接#xff1a;题目描述#xff1a;解法C 算法代码#xff1a; 题目链接#xff1a;
1314. 矩阵区域和 题目描述#xff1a; 解法
防止有人看不明白题目#xff0c;先解释一下题目 二维前缀和思想#xff1a; 使用前缀和矩阵 ret [x1,y1]~[x2,y2] D … 文章目录 题目链接题目描述解法C 算法代码 题目链接
1314. 矩阵区域和 题目描述 解法
防止有人看不明白题目先解释一下题目 二维前缀和思想 使用前缀和矩阵 ret [x1,y1]~[x2,y2] D (ABCD)-(AB)-(AC)A dp[x2,y2]-dp[x1-1,y2]-dp[x2,y1-1]dp[x1-1,y1-1] 重要的是怎么找到坐标answer[i][j] 这里要注意是坐标不是坐标系。
如果是(0,0)的话比0小的都要舍掉。同理比结尾大的也要舍掉。
我们可以处理一下 mn为边界。 还需要注意下标的映射关系。 ma矩阵是以(0,0)开始的前缀和dp矩阵是以(1,1)开始的。 从dp里面找(x,y)的时候要(x-1,y-1)才是mat里面的前缀和
从answer里面找(x,y)的时候要(x1,y1)才是dp里面的前缀和
所以我们要么改矩阵的面积公式要么在这里改 这样求到的就是dp表里面的坐标了。
前缀和矩阵 dp[i][j] 表示 mat 中从 (0,0) 到 (i-1,j-1) 矩形区域内的元素之和。
下面的结果矩阵ret就是answer C 算法代码
class Solution {public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int m mat.size(), n mat[0].size();vectorvectorint dp(m 1, vectorint(n 1));// 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];// 2. 使用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;}
};
