資訊專欄INFORMATION COLUMN
摘要：假設(shè)有一個(gè)整數(shù)數(shù)組，計(jì)算下標(biāo)從到包含和的數(shù)字的和。求和的請求將會(huì)在同一個(gè)整數(shù)數(shù)組上多次請求。這一題思路很簡單，因?yàn)?。而利用?dòng)態(tài)規(guī)劃則很容易知道。這里將原先的一維數(shù)組替換成二維數(shù)組。要求計(jì)算一個(gè)矩形內(nèi)的所有元素的值。
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.
假設(shè)有一個(gè)整數(shù)數(shù)組，計(jì)算下標(biāo)從i到j(luò)（包含i和j）的數(shù)字的和。求和的請求將會(huì)在同一個(gè)整數(shù)數(shù)組上多次請求。
這一題思路很簡單，因?yàn)?b>sum[i-j] = sum[0~j] - sum[0~(i-1)]。我們只需要通過一圈遍歷計(jì)算出每個(gè)下標(biāo)至0的所有數(shù)字的和即可。而利用動(dòng)態(tài)規(guī)劃則很容易知道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.
這里將原先的一維數(shù)組替換成二維數(shù)組。要求計(jì)算一個(gè)矩形內(nèi)的所有元素的值。
其實(shí)思路還是和原來一樣的，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);
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68701.html
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...
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...
摘要：表現(xiàn)在二進(jìn)制上的規(guī)律每次加上最末尾的求末尾的就拿這個(gè)數(shù)和它的補(bǔ)碼于。還有要求不是，要轉(zhuǎn)換一下，和之前那道的思路差不多。這里用一個(gè)的表示從到的和。 Range Sum Query - Immutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), i...
摘要：題目要求可以先參考數(shù)組不發(fā)生變動(dòng)時(shí)的題目。最后的葉節(jié)點(diǎn)為當(dāng)前數(shù)組的值，非葉結(jié)點(diǎn)則記錄了子數(shù)組的范圍以及該子數(shù)組中所有元素的和。它是一個(gè)非常輕量級的數(shù)據(jù)結(jié)構(gòu)，而且?guī)缀蹙褪菫檫@種題目量身打造。 題目要求 Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inc...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 1374·2021-10-09 09:44
閱讀 1451·2021-09-28 09:36
閱讀 16028·2021-09-22 15:55
閱讀 1254·2021-09-22 15:45
閱讀 2210·2021-09-02 09:48
閱讀 2794·2019-08-29 17:19
閱讀 2308·2019-08-29 10:54
閱讀 922·2019-08-23 18:40
