邯郸网站建设方案,地方网站如何做竞价,商城前端模板,成都微信小程序分类信息开发目录
#x1f388;了解题意
#x1f388;算法原理
#x1f388;实现代码 #x1f388;了解题意 给定一个大小为 m x n 的矩阵 mat 和一个整数 k#xff0c;你需要计算一个新的矩阵 answer#xff0c;其中每个 answer[i][j] 表示矩阵 mat 中以坐标 (i, j) 为中心、边…目录
了解题意
算法原理
实现代码 了解题意 给定一个大小为 m x n 的矩阵 mat 和一个整数 k你需要计算一个新的矩阵 answer其中每个 answer[i][j] 表示矩阵 mat 中以坐标 (i, j) 为中心、边长为 2*k1 的正方形区域内所有元素的和。
换句话说对于每个答案元素 ret[i][j]其值是由以 mat[i][j] 为中心、边长为 2*k1 的正方形区域内的所有元素之和组成的。以每个元素为中心的大小为 (2k1)*(2k1) 的子矩阵的元素之和。
mat是一个二维矩阵三行三列 k1的意思是每个下标对应的值向外都扩展1个单位将扩展1个单位后包含的所有数字都加起来就是最终的结果(还是该下标 就像图中所展现的一样1的位置开始向外扩展k个单位就是绿色包围的地方超过的范围区域不记剩下的是2451(这里需要加上1相加的结果是12所以ret结果数组的第一行第一列的数字是12.
按照这种方法我们依次扩展k个单位再依次相加就得到ret数组。 算法原理
我们首先需要预处理一个前缀和将每个子区间的前缀和进行计算但是我们需要知道上一篇的二维前缀和是从1开始而我们这一题是从0开始的但是我们预处理前缀和依旧是设定m1行n1列初始化为0. i和j都是从1开始的。 dp[i][j]dp[i-1][j]dp[i][j-1]arr[i-1][j-1]-dp[i-1][j-1]; 本题都是从1开始的所以我们要减去加上那个数需要将ij都减1我们打个比方我们要加上 下标[0][20],但是本题是从1开始那么对应的i1 j1,我们要加上对应的值的话我们需要将i-1,j-1.否则会导致结果不对。 这行代码声明了一个名为 dp 的二维 vector其大小为 (m1) x (n1)。其中dp[i][j] 表示矩阵中以 (i, j) 为右下角顶点的子矩阵的和。这样的声明方式初始化了一个大小为 (m1) x (n1) 的二维 vector并将其中的每个元素初始化为 0。 然后我们来使用前缀和我们需要的区间在横坐标的区间是i-k到ik纵坐标是j-k到jk 如果我们出现了下面的情况呢 我们看到(i-k,j-k)越过了0又或者(ik,jk)越过了(m,n),所以我们要在(i-k,j-k)0,0)取大值在(ik,jk),(m,n)取小值我们要防止越界情况。
注意如果正方形区域的边界超出了矩阵的边界则超出的部分将被视为 0 处理。 x1i-k max(0,i-k) 1 x2ik min(ik,m)1 y1j-k max(0,j-k) 1 y2jk min(jk,n)1 求x1,y1)到x2,y2)区间的前缀和 这里为什么1呢dp代表前缀和他是从1开始的那么如果我们要算某个特定区间的前缀和我们需要将区间1因为本题的mat数组下标从0开始。 最后我们就使用得出特定区间的前缀和
ret数组依旧是m行n列的初始化为0。 ret[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]; 实现代码
class Solution {
public:vectorvectorint matrixBlockSum(vectorvectorint mat, int k) {int mmat.size(),nmat[0].size();//1.预处理一个前缀和矩阵vectorvectorint dp(m1,vectorint(n1));for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1]-dp[i-1][j-1]mat[i-1][j-1];}}//使用vectorvectorint ret(m,vectorint(n));for(int i0;im;i){for(int j0;jn;j){int x1max(0,i-k)1,y1max(0,j-k)1;int x2min(m-1,ik)1,y2min(n-1,jk)1;ret[i][j]dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1];}}return ret;}
}; 慢不妨再慢点。
