差分算法介绍

一、基本概念

差分算法是前缀和算法的逆运算，可以快速的对数组的某一区间进行计算操作。

        例如，有一数列 a[1],a[2],.…a[n]，且令 b[i] = a[i]-a[i-1],b[1]=a[1]，那么就有
a[i] = b[1]+b[2]+.…+b[i] =
a[1]+a[2]-a[1]+a[3]-a[2]+.…+a[i]-a[i-1]，此时b数组称作a数组的差分数组
，换句话来说a数组就是b数组的前缀和数组  例：
     原始数组a：9  3  6  2  6  8
     差分数组b：9 -6  3 -4  4  2
可以看到a数组是b数组的前缀和数组。

那么现在有一个任务：对数组a区间[left,right]每个元素加一个常数c。这时可以利用原数组就是差分数组的前缀和这个特性，来解决这个问题。对于b数组，只需要执行

b[left] += c, b[right+1] −= c

二、leetcode例题

leetcode-1094-拼车
bool carPooling(vector<vector<int>>& trips, int capacity) { vector<int>
origin(1001,0); vector<int> difference(1001,0); int num; int left; int right;
int PrefixSum = 0; // 计算差分数组 for (int i = 0; i < trips.size(); ++i) { num =
trips[i][0]; left = trips[i][1]; right = trips[i][2]; difference[left] += num;
difference[right -1 + 1] -= num; } // 求差分数组的前缀和数组，即原数组 for (int i = 0; i <
difference.size(); ++i) { PrefixSum += difference[i]; origin[i] = PrefixSum; }
// 判断是否有超员 for (int i = 0; i < origin.size(); ++i) { if (origin[i] > capacity)
{ return false; } } return true; }
leetcode-1109-航班预定统计

 

• « 上一篇：QT制作TCP客户端
• » 下一篇：Java项目:嘟嘟网上商城系统(java+jdbc+jsp+mysql+ajax)