网站做友情链接,怎样把自己做的网站上传,电商网站建设选迅法网,局部翻新装修公司文章目录 题目303、区域和检索#xff08;数组不可变#xff09;304、二维区域和检索#xff08;矩阵不可变#xff09; 解①303#xff0c;一维前缀和②304#xff0c;二维前缀和 算法前缀和一维前缀和二维前缀和 题目
303、区域和检索#xff08;数组不可变#xff… 文章目录 题目303、区域和检索数组不可变304、二维区域和检索矩阵不可变 解①303一维前缀和②304二维前缀和 算法前缀和一维前缀和二维前缀和 题目
303、区域和检索数组不可变
给定一个整数数组 nums处理以下类型的多个查询:
计算索引 left 和 right 包含 left 和 right之间的 nums 元素的 和 其中 left right
实现 NumArray 类
NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 包含 left 和 right 两点也就是 nums[left] nums[left 1] ... nums[right] )
示例 1
输入
[NumArray, sumRange, sumRange, sumRange]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出
[null, 1, -1, -3]解释
NumArray numArray new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) 0 3)
numArray.sumRange(2, 5); // return -1 (3 (-5) 2 (-1))
numArray.sumRange(0, 5); // return -3 ((-2) 0 3 (-5) 2 (-1))304、二维区域和检索矩阵不可变
给定一个二维矩阵 matrix以下类型的多个请求
计算其子矩形范围内元素的总和该子矩阵的 左上角 为 (row1, col1) 右下角 为 (row2, col2) 。
实现 NumMatrix 类
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
示例 1 输入:
[NumMatrix,sumRegion,sumRegion,sumRegion]
[[[[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]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]解释:
NumMatrix numMatrix new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)解
①303一维前缀和
class Solution {public int[] productExceptSelf(int[] nums) {int lennums.length;int[] answernew int[len];answer[0]1;for(int i1;ilen;i){answer[i]nums[i-1]*answer[i-1];}int Rnums[len-1]; // R存储右侧所有元素乘积for (int i len - 2; i 0; i--) {answer[i] answer[i] * R;RR*nums[i];}return answer;}
}②304二维前缀和
class NumMatrix {int[][] sum;public NumMatrix(int[][] matrix) {int mmatrix.length,nmatrix[0].length;sumnew int[m1][n1];for(int i1;im;i){for(int j1;jn;j){sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]matrix[i-1][j-1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return sum[row21][col21]-sum[row1][col21]-sum[row21][col1]sum[row1][col1];}
}算法
前缀和
前缀和是一种常见的算法技巧用于快速计算数组中某个区间内元素的和通常用于优化处理大量的区间求和问题比如给定一个数组询问其中某个连续区间内元素的和。
算法原理 前缀和的核心思想是通过对数组进行预处理计算出从数组开头到每个位置的元素累加和然后利用这些预先计算好的累加和在O(1)时间内求出任意区间的和。假设给定数组为A其前缀和数组为prefix其中prefix[i]表示数组A从0到i的元素和。
一维前缀和
假设给定数组为A [1, 2, 3, 4, 5]其前缀和数组为prefix [1, 3, 6, 10, 15]。
但在①②中A数组的前缀和应当为prefix [0,1, 3, 6, 10, 15]比原数组要多一个。
在计算任意区间的和时通过在前缀和数组中添加0可以统一处理起始位置为0的边界情况无需单独考虑。例如对于查询区间[0, 3]直接使用prefix[3]即可得到结果无需特殊处理。
具体使用的时候建议用草稿纸绘制相关的数组或者矩阵的图形进行检验。
二维前缀和
二维的前缀和更为复杂
A [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
prefix [ [1, 3, 6], [5, 12, 21], [12, 27, 45] ]
prefix[i] [j] A[i] [j] prefix[i-1] [j] prefix[i] [j-1] - prefix[i-1] [j-1]
可以用下图帮助理解图源LeetCode负雪明烛 至于输出的公式也类似于上面的用右下角位置加上左上角-1的位置减去区域右上角和左下角
areasum[row21] [col21]-sum[row1] [col21]-sum[row21] [col1]sum[row1] [col1]为了方便书写代码实际矩阵比原矩阵大一圈所以这里所有的加减都在原矩阵基础上1
