304. Range Sum Query 2D - Immutable
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了304. Range Sum Query 2D - Immutable,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2516字,纯文字阅读大概需要4分钟。
内容图文
题目:
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).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
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
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
链接: http://leetcode.com/problems/range-sum-query-2d-immutable/
题解:
二维矩阵求Range Sum。这题我们也是用DP,不过dp的方法是: dp[i][j]等于从坐标matrix[0][0]到matrix[i - 1][j - 1]中所有元素的和。 这样我们就可以用中小学时计算矩形重叠面积的方法来计算出我们想要的结果。
Time Complexity - O(n2), Space Complexity - O(n2)。
public class NumMatrix { private int [][] sum; public NumMatrix(int[][] matrix) { if(matrix == null || matrix.length == 0) { return; } int rowNum = matrix.length, colNum = matrix[0].length; sum = newint[rowNum + 1][colNum + 1]; for(int i = 1; i < sum.length; i++) { for(int j = 1; j < sum[0].length; j++) { sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } } publicint sumRegion(int row1, int col1, int row2, int col2) { return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1]; } } // 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);
Reference:
https://leetcode.com/discuss/69047/clean-and-easy-to-understand-java-solution
https://leetcode.com/discuss/69424/clean-c-solution-and-explaination-o-mn-space-with-o-1-time
https://leetcode.com/discuss/69144/c-with-helper
https://leetcode.com/discuss/69054/dp-java-solution
https://leetcode.com/discuss/69045/sharing-my-python-solution
https://leetcode.com/discuss/71297/my-java-solution-only-used-6-ms
https://leetcode.com/discuss/69611/share-my-short-java-solution
https://leetcode.com/discuss/69435/my-c-solution-o-n-2-setup-o-1-sumregion
https://leetcode.com/discuss/69141/range-sum-query-2d-mutable-c-tree-array
https://leetcode.com/discuss/69137/short-python-solution-exactly-same-that-solves-range-query
https://leetcode.com/discuss/69117/c-solution-o-1-for-sumregion-function
原文:http://www.cnblogs.com/yrbbest/p/5050027.html
内容总结
以上是互联网集市为您收集整理的304. Range Sum Query 2D - Immutable全部内容,希望文章能够帮你解决304. Range Sum Query 2D - Immutable所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。