淄博网站外包,工作总结范文简短,郑州网站的建设,wordpress 编辑器 图片上传文章目录 1 前缀和数组1.1 题解1.2 Code1.3 结果 2 二维矩阵的前缀和数组2.1 题解2.2 Code2.3 结果 3 差分数组 1 前缀和数组
适用于快速频繁的计算一个索引区间内的元素之和#xff0c;核心思想就是使用一个前缀和数组#xff0c;然后使用前缀和数组的两个元素之差#xf… 文章目录 1 前缀和数组1.1 题解1.2 Code1.3 结果 2 二维矩阵的前缀和数组2.1 题解2.2 Code2.3 结果 3 差分数组 1 前缀和数组
适用于快速频繁的计算一个索引区间内的元素之和核心思想就是使用一个前缀和数组然后使用前缀和数组的两个元素之差来快速判断原来的数组的子数组之和具体如下题所示。 1.1 题解
前缀和数组的具体思路就是先new一个新的数组preSum出来preSum[i]记录的是nums[0…i-1]也就是nums数组中每一个元素的前缀和。比如preSum记录索引为0的元素的前缀和为2记录索引为1的元素的前缀和为-20-2索引为2元素的前缀和为-2031以此类推这样就能达到一个快速计算前缀和的一个技巧。
1.2 Code
class NumArray {
private:vectorintpreSum;
public:NumArray(vectorint nums) {preSum.resize(nums.size() 1);for (int i 1; i preSum.size(); i){preSum[i] preSum[i - 1] nums[i - 1];}}int sumRange(int left, int right) {return preSum[right 1] - preSum[left];}
};/*** Your NumArray object will be instantiated and called as such:* NumArray* obj new NumArray(nums);* int param_1 obj-sumRange(left,right);*/1.3 结果 2 二维矩阵的前缀和数组 2.1 题解
给定一个矩阵的左上角元素以及右下角元素就能知道矩阵的一个大小了现在题目给出这两个数值然后要求给出这个子矩阵的所有元素之和如上图就是红框内元素之和。因为这是矩阵的加减法可以用比较大的矩阵减去两个小矩阵再加回来多减的一个部分就能得到所求的结果。
2.2 Code
class NumMatrix {
// 定义preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private:vectorvectorint preSum;
public:NumMatrix(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();if (m 0 || n 0) return;//构造前缀和数组preSum.resize(m1, vectorint(n1));for (int i 1; i m; i){for (int j 1; j n; j){preSum[i][j] preSum[i-1][j] preSum[i][j-1] matrix[i - 1][j - 1] - preSum[i-1][j-1];}}}int sumRegion(int x1, int y1, int x2, int y2) {return preSum[x21][y21] - preSum[x1][y21] - preSum[x21][y1] preSum[x1][y1];}
};/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix* obj new NumMatrix(matrix);* int param_1 obj-sumRegion(row1,col1,row2,col2);*/2.3 结果 3 差分数组
差分数组主要适用场景主要是对原数组的某个区间的元素进行增减。前缀和是频繁求区间和差分数组是频繁修改某个区间的元素同时增加或者减少。比如同时给nums中所有元素加1再同时减2最后输出nums。
构造差分数组
vectorint diff;
diff.resize(nums.size());
diff[0] nums[0];//首元素就是nums的首元素
for (int i 1; i num.size(); i)
{diff[i] nums[i] - nums[i - 1];//后一项减前一项
}还原差分数组
vectorint res;
res.resize(diff.size());
res[0] diff[0];
for (int i 1; i diff.size(); i)
{res[i] res[i - 1] diff[i];
}有了diff数组之后想要给原数组当中索引为i到j的数同时加减就很简单了比如说对nums[i…j]当中进行整体加3就可以先对diff[i] 3再让diff[j1] -3这样就可以达到上述效果。
// 差分数组工具类
class Difference {// 差分数组private int[] diff;/* 输入一个初始数组区间操作将在这个数组上进行 */public Difference(int[] nums) {assert nums.length 0;diff new int[nums.length];// 根据初始数组构造差分数组diff[0] nums[0];for (int i 1; i nums.length; i) {diff[i] nums[i] - nums[i - 1];}}/* 给闭区间 [i, j] 增加 val可以是负数*/public void increment(int i, int j, int val) {diff[i] val;if (j 1 diff.length) {diff[j 1] - val;}}/* 返回结果数组 */public int[] result() {int[] res new int[diff.length];// 根据差分数组构造结果数组res[0] diff[0];for (int i 1; i diff.length; i) {res[i] res[i - 1] diff[i];}return res;}
}如力扣370题区间加法
