fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
小而美的算法技巧：差分数组 :: labuladong的算法小抄
这里的原数组 nums 对应的就是前缀和数组 prefixSum，差分数组 diff 对应的就是前缀和中的原数组 nums。
因此对于假前缀和数组第 [i,j] 位的加减操作，就可以理解为对原数组第 i 位加减某个数，第 j+1 位进行相反操作，就可以使前缀和数组表现为第 [i, j] 位同时加减某个数
如果trips = [[9,0,1]], capacity = 4 这情况应该是false. 因为一开始就不能进9个人. 所以应该多加一个检查 if (val > capacity) { return false; }
区间[i,j]增加 val
但是差分数组 一起增大的 差分数组中间不变（a + val - b-val） == a-b
只是差分数组的第一个和最后一个 这两个元素不同
i位置元素 diff[i] = diff[i] + val
j位置后面元素 diff[j+1] = diff[i+1] - val
这里是不是应该注释一下，nums[i] 表示 站点 i 到站点 i+1 之间的乘客人数。由此，虽然有1001个站点，但是 nums 的长度只要 1000 就可以了。
利用东哥的差分数组，解决力扣：1094. 拼车，原理一样，代码简单优化了下：
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] diff=new int[1000+1];
int maxLen=1;
for(int[] trip:trips){
int i=trip[1],j=trip[2],val=trip[0];
maxLen=Math.max(maxLen,j);//maxLen记录最大的公里数
updateDiff(diff,i,j,val);
}
return convertDiff(diff,maxLen,capacity);
}
//更新差分数组，公里数为[i,j-1]的增加val
public void updateDiff(int[] diff,int i,int j,int val){
diff[i]+=val;
diff[j]-=val;
}
public boolean convertDiff(int[] diff,int maxLen,int capacity){
if(diff[0]>capacity) return false;
for(int i=1;i<=maxLen;i++){
diff[i]=diff[i-1]+diff[i];
//判断是否超载
if(diff[i]>capacity) return false;
}
return true;
}
}
区间加法：
class Solution {
vector<int> diff;
public:
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
vector<int> A;//初始数组
A.resize(length);
diff=differ(A);
for(int i=0;i<updates.size();i++){
int start=updates[i][0];
int end=updates[i][1];
int val=updates[i][2];
diff=increment(start,end,val);
}
return result();
}
//update{start,end,inc}
vector<int> differ(vector<int>& A){//构造差分数组
int n=A.size();
diff.resize(n);
diff[0]=A[0];
for(int i=1;i<diff.size();i++){
diff[i]=A[i]-A[i-1];
}
return diff;
}
vector<int> increment(int start,int end,int val){//
diff[start]+=val;
if(end+1<diff.size()){//此处为end+1
diff[end+1]-=val;
}
return diff;
}
vector<int> result(){
vector<int> res;
res.resize(diff.size());
res[0]=diff[0];
for(int i=1;i<res.size();i++){
res[i]=res[i-1]+diff[i];
}
return res;
}
};
python实现打卡🥰
class Diff:
def __init__(self,nums) -> None:
self.diff = [nums[0]]
for i in range(1, len(nums)):
self.diff.append(nums[i]-nums[i-1])
pass
def increment(self, i, j, val):
self.diff[i] +=val
if j+1 < len(self.diff):
self.diff[j+1] -=val
def cal(self, cap):
res = 0
for i in range(len(self.diff)):
res += self.diff[i]
if res > cap:
return False
return True
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
df = Diff([0]*1001)
for i in trips:
df.increment(i[1],i[2]-1,i[0])
return df.cal(capacity)
优化了一下 拼车
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
// 0 <= fromi < toi <= 1000 最多有一千零1个车站
vector<int> res(1001, 0);
for(auto trip : trips){
res[trip[1]] += trip[0];
if(trip[2] < res.size()){
res[trip[2]] -= trip[0];
}
}
for(int i = 1; i < res.size(); i++){
res[i] += res[i-1];
}
for(auto r : res){
if(r > capacity){
return false;
}
}
return true;
}
};
