- 浏览: 185069 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a 2D matrix matrix[][], find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given matrix = [
[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]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
这道题目属于二维的矩阵运算,题目中假设矩阵没有变化,对比前面的一道题Range Sum Query - Mutable来看,我们也可以用树状数组来做,这里我们就需要构建一个二维的树状数组。具体如何构建一个树状数组请看连接中的那道题。这里先给出一个AC的代码:
代码中注释的部分是update方法,对应mutable的情况。
因为树状数组的优势在于解决对变化的数据求和,在不变的情况下,优势就没有那么明显,因为构建一个树状数组也需要消耗时间和空间。这道题我们采用动态规划的思想解决比较合适。
代码如下:
Example:
Given matrix = [
[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]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
这道题目属于二维的矩阵运算,题目中假设矩阵没有变化,对比前面的一道题Range Sum Query - Mutable来看,我们也可以用树状数组来做,这里我们就需要构建一个二维的树状数组。具体如何构建一个树状数组请看连接中的那道题。这里先给出一个AC的代码:
public class NumMatrix { int[][] matrix; int[][] BIT; public NumMatrix(int[][] matrix) { this.matrix = matrix; if(matrix == null || matrix.length == 0 ) return; BIT = new int[matrix.length + 1][matrix[0].length + 1]; for(int i = 0; i < matrix.length; i++) for(int j = 0; j < matrix[0].length; j++) init(i, j, matrix[i][j]); } public void init(int i, int j, int val) { j ++; while(j <= matrix[0].length) { BIT[i][j] += val; j += (j & -j); } } /* implement mutable public void update(int i, int j, int val) { int differ = val - matrix[i][j]; matrix[i][j] = val; init(i, j, differ); } */ public int sumRegion(int row1, int col1, int row2, int col2) { int result = 0; for(int i = row1; i <= row2; i++) { result += getSumRange(i, col1, col2); } return result; } public int getSumRange(int i, int start, int end) { return getSum(i, end) - getSum(i, start - 1); } public int getSum(int i, int point) { point ++; int sum = 0; while(point > 0) { sum += BIT[i][point]; point -= (point & -point); } return sum; } } // Your NumMatrix object will be instantiated and called as such: // NumMatrix numMatrix = new NumMatrix(matrix); // numMatrix.sumRegion(0, 1, 2, 3); // numMatrix.sumRegion(1, 2, 3, 4);
代码中注释的部分是update方法,对应mutable的情况。
因为树状数组的优势在于解决对变化的数据求和,在不变的情况下,优势就没有那么明显,因为构建一个树状数组也需要消耗时间和空间。这道题我们采用动态规划的思想解决比较合适。
代码如下:
public class NumMatrix { int[][] dp; public NumMatrix(int[][] matrix) { if(matrix == null || matrix.length == 0) return; dp = new int[matrix.length + 1][matrix[0].length + 1]; for(int i = 1; i <= matrix.length; i++) { for(int j = 1; j <= matrix[0].length; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + matrix[i - 1][j - 1] - dp[i - 1][j - 1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1] - dp[row1][col2 + 1]; } } // Your NumMatrix object will be instantiated and called as such: // NumMatrix numMatrix = new NumMatrix(matrix); // numMatrix.sumRegion(0, 1, 2, 3); // numMatrix.sumRegion(1, 2, 3, 4);
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 270Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 271You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 390Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 379Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 504Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 568Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 483Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 672Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 474The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 435Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 584Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 592Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 429All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 906Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 935Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 607Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 694Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 861Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 791You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 728For a undirected graph with tre ...
相关推荐
java java_leetcode题解之Range Sum Query - Immutable.java
dot-prop-immutable, 点prop的不可变版本,带有一些扩展名 dot-prop-immutable 点prop的不可变版本,带有一些扩展名。npm install dot-prop-immutable这个模块的动机是在不改变普通JavaScript对象的现有状态的情况
了解了redux-immutable的基本用法后,我们来看看压缩包中的文件`redux-immutable-master`。这通常代表了项目的源代码仓库,包含项目的根目录、README文件、源码、测试文件、配置文件等。开发者可以通过查看源码来...
在`chai-immutable-master`压缩包中,包含的是`chai-immutable`项目的源代码。通常,这样的项目会包含以下组成部分: 1. **源码**:主要位于`src`目录下,这是实现`chai-immutable`核心功能的JavaScript代码。 2. *...
**前端开源库-typed-immutable** 在前端开发中,数据管理是至关重要的,尤其是在大型应用中,保持数据的一致性和可预测性对于代码的维护和性能优化有着决定性的作用。`typed-immutable`是一个专门为JavaScript设计...
`seamless-immutable` 是一个专门针对JavaScript设计的不可变数据结构库,它为开发者提供了与原生JavaScript数组和对象兼容的接口,同时确保了数据一旦创建就无法被修改。这个库的核心理念是为了帮助开发者实现更...
leetcode 2 和 c 90 天代码 从今天开始,在接下来的 90 天里,我将开始一段使用 C++ ...Immutable() ...问题二:Range Sum Query 2D - Immutable() 问题 3:重复 () 问题 4:从排序数组中删除重复项
16. **Range Sum Query 2D - Immutable** (二维不可变范围求和) 类似于一维,但在二维数组上进行范围求和。可以使用二维前缀和。 17. **Longest Increasing Subsequence** (最长递增子序列) 寻找数组中最长的严格...
go-immutable-radix, 在Golang中,一个不可变的基数树实现 go-immutable-radix 提供实现不可变 radix的iradix 包。 包只提供单个 Tree 实现,针对稀疏节点优化。作为一个基数树,它提供以下内容:O(k) 操作。在许多...
"前端开源库-immutable-instance-id"就是这样一个工具,它的主要功能是为每个进程实例生成一个唯一的、不可变的ID。这个ID在进程运行期间保持不变,确保了在多线程或者分布式环境中的数据追踪和标识的独特性。 不可...
**前端开源库-immutable-core详解** 在前端开发领域,优化性能和提高代码可维护性是开发者不断追求的目标。为此,各种工具和库应运而生,其中“immutable-core”是一个非常重要的概念,它代表着一种不可变数据处理...
ToDo-react-redux-immutable, ToDo应用显示使用反应,重现和ImmutableJS的最佳实践 技巧,技巧和最佳实践,使用反应,重现和 ImmutableJS请检查文章解释逻辑> ...ToDo应用演示如何使用Red
CKS - Practise Immutable Resource
在编程领域,不可变对象(Immutable Object)是一种重要的设计模式,尤其在多线程和并发环境中,它提供了安全性和性能优化。在这个初学者教程中,我们将深入探讨C#中的不可变对象,包括“内部不变性”和“观察不变性...
Range Sum Query 2D - Immutable **知识点:** - **问题描述:** - 给定一个只读的二维整数数组,需要高效地查询任意两个坐标之间元素之和。 - **解决方案分析:** - **二维前缀和:** - 构建一个二维前缀...
给定两个对象,获取它们之间的Seamless-immutable-diff 安装 如果尚未下载node,请从下载并安装。 npm install seamless-immutable-diff --save 用法 import diff from 'seamless-immutable-diff' ; import ...
在Kotlin编程语言中,`kotlinx.collections.immutable`是一个重要的库,它提供了不可变集合的实现。不可变集合是一旦创建后就不能修改的集合,这种数据结构在多线程环境、函数式编程和构建安全的数据模型时非常有用...
**前端开源库 Immutable.js** Immutable.js 是一个 JavaScript 库,由 Facebook 的 React 团队开发并维护,它为开发者提供了一种在前端开发中高效处理数据的方法。该库的核心概念是不可变数据,即一旦创建,数据就...
article-json-immutable-methods 文章json的不可变方法安装如果尚未下载node,请从下载并安装。 npm install article-json-immutable-methods --save测验npm installnpm test依存关系 :通常可变数组方法的不可变...