leetcode303-304 Range Sum Query Immutable

Worktile 發布于2019-08-15 14:35 / 2152人閱讀

摘要：假設有一個整數數組，計算下標從到包含和的數字的和。求和的請求將會在同一個整數數組上多次請求。這一題思路很簡單，因為。而利用動態規劃則很容易知道。這里將原先的一維數組替換成二維數組。要求計算一個矩形內的所有元素的值。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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