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,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 矩阵区域和内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 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

  • 动态规划之矩阵连乘问题Python实现方法

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125.

  • Java实现LeetCode（螺旋矩阵）

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • C++实现LeetCode(130.包围区域)

    [LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O

  • C++验证LeetCode包围区域的DFS方法

    验证LeetCode Surrounded Regions 包围区域的DFS方法 在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<

  • Ruby实现的矩阵连乘算法

    动态规划解决矩阵连乘问题,随机产生矩阵序列,输出形如((A1(A2A3))(A4A5))的结果. 代码: #encoding: utf-8 =begin author: xu jin, 4100213 date: Oct 28, 2012 MatrixChain to find an optimum order by using MatrixChain algorithm example output: The given array is:[30, 35, 15, 5, 10, 20, 25]

  • C++ LeetCode542矩阵示例详解

    目录 LeetCode  542.01 矩阵 方法一:广度优先搜索 AC代码 C++ LeetCode  542.01 矩阵 力扣题目链接:leetcode.cn/problems/01… 给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离. 两个相邻元素间的距离为 1 . 示例 1: 输入:mat = [[0,0,0],[0,1,0],[0,0,0]]输出:[[0,0,0],[0,1,0],[0,0,0]] 示例

  • 最短时间学会基于C++实现DFS深度优先搜索

    最短时间学会基于C++实现DFS深度优先搜索

    目录 前言 1.迷宫找出口,区分dfs,bfs: 一.DFS经典放牌可能组合 二.leetcode 员工的重要性 三.leetcode 图像渲染 四.leetcode 被围绕的区域 五.岛屿数量 六. 小练习:岛屿的最大面积 总结 前言 同学们肯定或多或少的听到过别人提起过DFS,BFS,却一直都不太了解是什么,其实两个各为搜索算法,常见使用 深度优先搜索(DFS) 以及 广度优先搜索(BFS) ,今天我们就来讲讲什么是深度优先搜索,深度优先就是撞到了南墙才知道回头,才会往上一层返回. 1.迷宫

  • Python爬虫实例_利用百度地图API批量获取城市所有的POI点

    上篇关于爬虫的文章,我们讲解了如何运用Python的requests及BeautifuiSoup模块来完成静态网页的爬取,总结过程,网页爬虫本质就两步: 1.设置请求参数(url,headers,cookies,post或get验证等)访问目标站点的服务器: 2.解析服务器返回的文档,提取需要的信息. 而API的工作机制与爬虫的两步类似,但也有些许不同: 1.API一般只需要设置url即可,且请求方式一般为"get"方式 2.API服务器返回的通常是json或xml格式的数据,解析更简

随机推荐