LeetCode 动态规划之矩阵区域和详情

LeetCode 动态规划之矩阵区域和详情

目录题目题解解题分析解题代码

题目

矩阵区域和

给你一个 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[][]

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)

解题代码

题解代码如下（代码中有详细的注释说明）：

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,yQMhyAAvZpy2;

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;

}

}

提交后反馈结果（由于该题目没有进行优化，性能一般）：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。