leetcode303-304 Range Sum Query Immutable

Worktile 发布于2019-08-15 14:35 / 2127人阅读

摘要：假设有一个整数数组，计算下标从到包含和的数字的和。求和的请求将会在同一个整数数组上多次请求。这一题思路很简单，因为。而利用动态规划则很容易知道。这里将原先的一维数组替换成二维数组。要求计算一个矩形内的所有元素的值。

Range Sum Query Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

假设有一个整数数组，计算下标从i到j（包含i和j）的数字的和。求和的请求将会在同一个整数数组上多次请求。

这一题思路很简单，因为sum[i-j] = sum[0~j] - sum[0~(i-1)]。我们只需要通过一圈遍历计算出每个下标至0的所有数字的和即可。而利用动态规划则很容易知道sum[0~j] = sum[0~j-1] + num[j]。

    private int[] sum;
    public NumArray(int[] nums) {
        this.sum = new int[nums.length];
        for(int i = 0 ; i
Range Sum Query Immutable II
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).

Range Sum Query 2D
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.
这里将原先的一维数组替换成二维数组。要求计算一个矩形内的所有元素的值。
其实思路还是和原来一样的，sum(row1, column1, row2, column2) = sum(0,0,row2, col1-1) + sum(0,0,row1-1, col2) - sum(0,0,row1-1, col1-1)。这里需要排除一些特殊情况，比如row1=1或是col1=1等。
    private int[][] sum;
    public NumMatrix(int[][] matrix){
        int row = matrix.length;
        if(row==0) {sum = new int[0][0]; return;}
        int column = matrix[0].length;
        sum = new int[row][column];
        
        for(int i = 0 ; i0? sum[row1-1][col2] : 0 )- (col1>0 ? sum[row2][col1-1] : 0) + (row1>0 && col1>0 ? sum[row1-1][col1-1] : 0);
    }
    

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Immutable immutable-js Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68701.html

[LeetCode] 304. Range Sum Query 2D - Immutable

Problem 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). https://leetcode.com/static/i...s...

chinafgj 2019-08-16 13:43 评论0 收藏0
[LeetCode] Range Sum Query Immutable

Problem Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRan...

LiuZh 2019-08-14 14:02 评论0 收藏0
Range Sum Query

摘要：表现在二进制上的规律每次加上最末尾的求末尾的就拿这个数和它的补码于。还有要求不是，要转换一下，和之前那道的思路差不多。这里用一个的表示从到的和。 Range Sum Query - Immutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), i...

zhongmeizhi 2019-08-14 17:19 评论0 收藏0
leetcode307. Range Sum Query - Mutable

摘要：题目要求可以先参考数组不发生变动时的题目。最后的叶节点为当前数组的值，非叶结点则记录了子数组的范围以及该子数组中所有元素的和。它是一个非常轻量级的数据结构，而且几乎就是为这种题目量身打造。题目要求 Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inc...

Lemon_95 2019-08-15 14:35 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0