摘要:假设有一个整数数组,计算下标从到包含和的数字的和。求和的请求将会在同一个整数数组上多次请求。这一题思路很简单,因为。而利用动态规划则很容易知道。这里将原先的一维数组替换成二维数组。要求计算一个矩形内的所有元素的值。
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 ; iRange 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); }
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.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...
摘要:表现在二进制上的规律每次加上最末尾的求末尾的就拿这个数和它的补码于。还有要求不是,要转换一下,和之前那道的思路差不多。这里用一个的表示从到的和。 Range Sum Query - Immutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), i...
摘要:题目要求可以先参考数组不发生变动时的题目。最后的叶节点为当前数组的值,非叶结点则记录了子数组的范围以及该子数组中所有元素的和。它是一个非常轻量级的数据结构,而且几乎就是为这种题目量身打造。 题目要求 Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inc...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
阅读 1357·2021-10-09 09:44
阅读 1440·2021-09-28 09:36
阅读 15927·2021-09-22 15:55
阅读 1238·2021-09-22 15:45
阅读 2199·2021-09-02 09:48
阅读 2783·2019-08-29 17:19
阅读 2296·2019-08-29 10:54
阅读 906·2019-08-23 18:40