Python 官方文档:入门教程 => 点击学习
目录题目题解解题分析解题代码题目 矩阵区域和 给你一个 m x n 的矩阵 mat 和一个整数 k ,请你返回一个矩阵&n
矩阵区域和
给你一个 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
解题思路:
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
根据前缀矩阵计算结果:
解题代码如下所示:
复杂度
O(M * N)
O(M * N)
题解代码如下(代码中有详细的注释说明):
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length,n = mat[0].length;
int[][] dp = get_dp(mat,m,n);
return get_res(dp,m,n,k);
}
//获取dp数组
public int[][] get_dp(int[][] arr,int m,int n){
int[][] dp = new int[m+1][n+1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j];
return dp;
}
//获取结果
public int[][] get_res(int[][] dp,int m,int n,int k){
int[][] res = new int[m][n];
int x1,y1,x2,y2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
x1 = Math.max(0,i-k);y1 = Math.max(0,j-k);
x2 = Math.min(m,i+k+1);y2 = Math.min(n,j+k+1);
res[i][j] = dp[x2][y2]-dp[x1][y2]-dp[x2][y1]+dp[x1][y1];
}
}
return res;
}
}
提交后反馈结果(由于该题目没有进行优化,性能一般):
到此这篇关于LeetCode 动态规划之矩阵区域和详情的文章就介绍到这了,更多相关LeetCode 矩阵区域和内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: LeetCode 动态规划之矩阵区域和详情
本文链接: https://www.lsjlt.com/news/146888.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0