一、sort函数
sort函数的头文件为: #include;
常用格式:sort(vec.begin(),vec.end()) :对向量进行升序排列;
sort(num,num+n):对数组num的0~n-1元素进行升序排序。
如果想要降序排列:sort(begin_pointer,begin_pointer+n,cmp)
其中,可以调用自己定义的cmp函数达到降序排列的目的
bool cmp(int a,int b) { return a>b; }
二、swap函数
swap函数的头文件为: #include
因为 swap 函数的参数是两个地址,所以这样调用它:
swap(&i, &j);
作用为:交换两个数值的值
C++也可以使用引用,swap 可以这样写:
void swap(int &a, int &b) { int k = a; a = b; b = k; }
三、前缀和
前缀和的思路是这样的,对于一个给定的数组 nums,我们额外开辟一个前缀和数组进行预处理:
int n = nums.length; // 前缀和数组 int[] preSum = new int[n + 1]; preSum[0] = 0; for (int i = 0; i < n; i++) preSum[i + 1] = preSum[i] + nums[i];
这个前缀和数组 preSum 的含义,preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和,只需要一步 *** 作 preSum[j+1]-preSum[i] 即可,而不需要重新去遍历数组了。
四、差分
如果数组A是B的前缀和,则B是A的差分。
我们构造一个数组的差分矩阵,是为了针对频繁的对数组中某个区间进行同一 *** 作。例如将序列中[l, r]之间的每个数加上c这一 *** 作,可能执行n次,每次的c不同,如果对原数组进行 *** 作,每次 *** 作都会花费O(n)的时间复杂度。如果使用该数组的差分数组进行 *** 作,每次 *** 作为O(1)。然后求差分数组的前缀和即为所求结果。
差分数组
针对[l, r]之间的每个数加上c这一 *** 作
let diffCreate = (c, l, r) => { diffArr[l] += c; diffArr[r + 1] -= c; }
这是差分数组 *** 作的核心,对于原数组区间中每个数都要 *** 作,而差分数组就只要 *** 作两个数。因为原数组是差分数组的前缀和,所以第l个数加c,后面每个数都会加c,再把不需要的部分(r后面的数)减去c。
针对原数组快速构造差分数组
把原数组a看作全0数组b,每个位置上的数看作一次差分 *** 作。比如说如果a[1]=2,那么对全0数组b进行diffCreate(1,1,2) *** 作,相当于把从1到1区间(其实就一个数)上的每个数加2。所有的数 *** 作后得到的b就是a的差分数组。
差分矩阵也是同理。
let diffCreate = (c, x1, y1, x2, y2) => { diffArr[x1][y1] += c; diffArr[x2 + 1][y1] -= c; diffArr[x1][y2 + 1] -= c; diffArr[x2 + 1][y2 + 1] += c; }
注意:不论是差分数组还是差分矩阵下标都要从1开始(a[1]、a[2][3]),而且前面的0位置(a[0]、a[0][0]、a[1][0])都要置为0。因为求前缀和时(也就是求原数组)会用到,为了同一 *** 作而不对0处进行特殊判断,所以为0写起来更方便。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)