题目
矩阵区域和
给你一个 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]]
提示：
|
1
2
3
4
|
m == mat.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100 |
题解
解题分析
解题思路：
- 本题是以典型的动态规划问题；
- 获取前缀矩阵dp[][]
|
1
|
dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]+arr[i][j]-dp[i][j]; |
根据前缀矩阵计算结果：
- 核心问题转化为了：1).求这两个过程的转移方程；2). 边界处理.
解题代码如下所示：
复杂度
-
时间复杂度：
O(M * N) -
空间复杂度：
O(M * N)
解题代码
题解代码如下（代码中有详细的注释说明）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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 矩阵区域和内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://juejin.cn/post/7083104853047640094
