济南建手机网站公司,广东建设安全员报名网站,河北保定网站建设,网站设计搜索栏怎么做个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【Leetcode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给你一个 m x n 的矩阵 mat 和一个整数 k 请你返回一个矩阵 answer 其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和
i - k r i kj - 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.lengthn mat[i].length1 m, n, k 1001 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: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] mat[i - 1][j - 1] - dp[i - 1][j - 1];// 使用前缀和矩阵vectorvectorint answer(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,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;}
};最后就通过啦
