算法专题：差分数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法专题：差分数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前置知识

构建一个差分数组

void func(int * lb1,int len)
{
    int * lb2=new int [len];
    lb2[0]=lb1[0];
    for (int i=1;i<len;i++)
        lb2[i]=lb1[i]-lb1[i-1];
}

操作一个连续区间

void func(int * lb,int len1,int begin,int len2,int x)
{
    lb[begin]+=x;
    if (begin+len2<len1)
        lb[begin+len2]-=x;
}

练习习题

1094. 拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int lb[1001] {};
        for (int i=0;i<trips.size();i++)
        {
            lb[trips[i][1]]+=trips[i][0];
            lb[trips[i][2]]-=trips[i][0];
        }
        int count=0;
        for (int i=0;i<1001;i++)
        {
            count+=lb[i];
            if (count>capacity) return false;
        }
        return true;
    }
};

1109. 航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        int * lb=new int [n+1];
        for (int i=0;i<n+1;i++) lb[i]=0;
        for (int i=0;i<bookings.size();i++)
        {
            lb[bookings[i][0]-1]+=bookings[i][2];
            lb[bookings[i][1]]-=bookings[i][2];
        }
        vector<int> result(n,0);result[0]=lb[0];
        for (int i=1;i<n;i++)
            result[i]=result[i-1]+lb[i];
        delete [] lb;
        return result;
    }
};

1450. 在既定时间做作业的学生人数

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int time[1000] {};
        for (int i=0;i<startTime.size();i++)
        {
            time[startTime[i]-1]+=1;
            if (endTime[i]<1000) time[endTime[i]]-=1;
        }
        for (int i=1;i<1000;i++)
            time[i]=time[i-1]+time[i];
        return time[queryTime-1];
    }
};

2406. 将区间分为最小组数

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        //1e6是双精度浮点数
        int lb[int(1e6+1)] {};
        for (int i=0;i<intervals.size();i++)
        {
            lb[intervals[i][0]-1]+=1;
            lb[intervals[i][1]]-=1;
        }
        int result=lb[0],count=lb[0];
        for (int i=1;i<1e6;i++)
        {
            count=count+lb[i];
            if (count>result) result=count;
        }
        return result;
    }
};

2381. 字母移位II

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int * lb1=new int [s.size()+1];
        for (int i=0;i<s.size()+1;i++) lb1[i]=0;
        for (int i=0;i<shifts.size();i++)
        {
            int x=shifts[i][2]==1?1:-1;
            lb1[shifts[i][0]]+=x;lb1[shifts[i][1]+1]-=x;
        }
        int * lb2=new int [s.size()];lb2[0]=lb1[0];
        for (int i=1;i<s.size();i++)
            lb2[i]=lb2[i-1]+lb1[i];
        string result;
        for (int i=0;i<s.size();i++)
        {
            int x=lb2[i];x+=26*1e5;x%=26;
            if (s[i]+x<='z') result+=char(s[i]+x);
            else result+=char(s[i]+x-26);
        }
        delete [] lb1;delete [] lb2;
        return result;
    }
};

2772. 使数组中的所有元素都等于零

class Solution {
public:
    bool checkArray(vector<int> &nums, int k) {
        int * lb=new int [nums.size()];
        for (int i=0;i<nums.size();i++) lb[i]=0;
        lb[0]=nums[0];
        for (int i=1;i<nums.size();i++)
            lb[i]=nums[i]-nums[i-1];
        for (int i=0;i<nums.size()-k;i++)
        {
            if (lb[i]<0) return false;
            lb[i+k]+=lb[i];
        }
        for (int i=nums.size()-k+1;i<nums.size();i++)
            if (lb[i]!=0) return false;
        delete [] lb;
        return true;
    }
};