本文介绍: 每日OJ题_算法_前缀和⑧_力扣1314. 矩阵区域和(二维前缀和)
目录
力扣1314. 矩阵区域和
难度 中等
给你一个 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
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
}
};
解析代码
题意有点类似C语言写过的三子棋的一个功能?要返回的二维数组就是原数组上下左右移动K的单位包起来的正方形区域所有元素的和(越界的不管),用二维前缀和思路解决。
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j) // 此题的mat下标不是从1开始的,注意转化
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
vector<vector<int>> ret(m, vector<int>(n));
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
int x1 = max(0, i - k) + 1; // 左上角
int y1 = max(0, j - k) + 1;
int x2 = min(m - 1, i + k) + 1; // 右下角
int 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;
}
};
原文地址:https://blog.csdn.net/GRrtx/article/details/135902736
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_65769.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。