leetcode304. 二维区域和检索 - 矩阵不可变(java)

这篇具有很好参考价值的文章主要介绍了leetcode304. 二维区域和检索 - 矩阵不可变(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二维区域和检索 - 矩阵不可变

难度 - 中等
原题链接 - 二维区域和检索 - 矩阵不可变

题目描述

给定一个二维矩阵 matrix,以下类型的多个请求:
计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。
实现 NumMatrix 类:
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例1:
leetcode304. 二维区域和检索 - 矩阵不可变(java),数据结构,算法,java,矩阵,java,线性代数,算法,leetcode,数据结构,排序算法
输入:
[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 1e5
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

leetcode304. 二维区域和检索 - 矩阵不可变(java),数据结构,算法,java,矩阵,java,线性代数,算法,leetcode,数据结构,排序算法

前缀和

和一维数组类似.也是先定义一个前缀和数组,求出前缀和的值,然后调用区间值时,就可以用前缀和进行计算.
注意:前缀和数组下标从1开始.
leetcode304. 二维区域和检索 - 矩阵不可变(java),数据结构,算法,java,矩阵,java,线性代数,算法,leetcode,数据结构,排序算法

代码演示

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m > 0) {
            int n = matrix[0].length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }

}

一维数组前缀和

leetcode303. 区域和检索 - 数组不可变文章来源地址https://www.toymoban.com/news/detail-664036.html

到了这里,关于leetcode304. 二维区域和检索 - 矩阵不可变(java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode303. 区域和检索 - 数组不可变(java)

    难度 - 简单 原题链接 - 区域和检索 - 数组不可变 给定一个整数数组 nums,处理以下类型的多个查询: 计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left = right 实现 NumArray 类: NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 num

    2024年02月12日
    浏览(42)
  • java数据结构与算法刷题-----LeetCode240. 搜索二维矩阵 II

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 法一:把整个数组遍历一遍,时间复杂度O(m*n) 法二:每一行用二分搜索,那么时间复杂度就是O(m * l o g 2 n log_2{n} l o g

    2024年01月22日
    浏览(56)
  • leetcode 74. 搜索二维矩阵(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/search-a-2d-matrix 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回

    2024年02月16日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(43)
  • java数据结构与算法刷题-----LeetCode766. 托普利茨矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 这道题只要换一种理解方式,瞬间就会变的很简单。 题目描述是每个元素左上和右下对角线元素都相同。但是,我们发

    2024年01月25日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode378. 有序矩阵中第 K 小的元素

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 已知矩阵相对有序,可以用二分搜索,不过和一维数组排序不同,这是二维的 每一行都递增,每一列也是递增,所以每

    2024年01月23日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和

    2024年04月26日
    浏览(45)
  • Leetcode74. 搜索二维矩阵

    给你一个满足下述两条属性的  m x n  整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数  target  ,如果  target  在矩阵中,返回  true  ;否则,返回  false  。    

    2024年02月11日
    浏览(31)
  • LeetCode【74】搜索二维矩阵

    题目: 代码:

    2024年02月07日
    浏览(43)
  • 【LeetCode】74. 搜索二维矩阵

    思路 总体思路 由于二维矩阵固定列的「从上到下」或者固定行的「从左到右」都是 升序 的 因此我们可以使用 两次二分 来定位到目标位置。 第一次二分: 从第 0 列中的「所有行」开始找,找到合适的行 row, 即找到最后一个满足 matrix[x][0] = target 的行号; 第二次二分:从

    2024年02月09日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包