前缀和、差分思想

简介: 前缀和、差分思想


前缀和

  • 一维数组A
  • 前缀和数组S
  • 子段和——A中第l个数到第r个数的和
  • 当A中都是非负数时,前缀和数组S单调递增

实战

1248.统计 [优美子数组]

https://leetcode.cn/problems/count-number-of-nice-subarrays/

奇数看作1,偶数看作О,求前缀和数组S

连续子数组[Lr]中的奇数个数为S[r]-S[l一1]

枚举右端点i,只需找到i前面有多少个j满足S[i] -Si]= k

由于S单调递增,只要满足S[i]-S[ji]=k (k > 0),j必然在i前面

所以只需用一个计数数组统计S中每个值的个数

枚举右端点i,看一下等于S[i]-k的值有几个就行了

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        //源问题
        //sum(l,r)==k
        int n=nums.size();
        vector<int> s(n+1);
        s[0]=0;
        for(int i=1;i<=n;i++) s[i]=s[i-1]+nums[i-1]%2;
        vector<int> count(n+1);
        int ans=0;
        count[s[0]]++;
        for(int i=1;i<=n;i++)
        {
            if(s[i]-k>=0) ans+=count[s[i]-k];
            count[s[i]]++;
        }
        return ans;
    }
};

53.最大子数组和

https://leetcode.cn/problems/maximum-subarray/

解法一:前缀和+前缀最小值

求出前缀和数组S,枚举右端点i,需要找到i之前的一个j使得S[i]-S[]最大

也就是要让S[]最小,再维护一个S的前缀最小值即可

“前缀和”算法不只局限于求和,也可以扩展到前缀最小值、最大值等

解法二:贪心

只要“和”是正的,就不断向右扩展一旦发现“和”是负的,立即舍弃

如果需要方案,用双指针维护当前取的范围即可

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // int pre = 0, maxAns = nums[0];
        // for (const auto &x: nums) {
        //     pre = max(pre + x, x);
        //     maxAns = max(maxAns, pre);
        // }
        // return maxAns;
        int n=nums.size();
        vector<int> dp(n+1,0);
        dp[0]=nums[0];
        int mmax=dp[0];
        for(int i=1;i<n;i++)
        {
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            mmax=max(mmax,dp[i]);
        }
        return mmax;
    }
};

二维前缀和

  • 二维数组A
  • 前缀和数组S

  • 子矩阵和——以(p,q)为左上角、(i,j)为右下角的A的子矩阵中数的和

实战

304.二维区域和检索–矩阵不可变

https://leetcode.cn/problems/range-sum-query-2d-immutable/

class NumMatrix {
public:
    vector<vector<int>> sums;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
};

差分

  • 一维数组A
  • 差分数组B
  • 其中B1=A1,Bi= Ai-Ai-1(2≤ i ≤n)
  • 差分数组B的前缀和数组就是原数组A
  • 把A的第l个数到第r个数加d,B的变化为:Bl加d,Br+1减d

实战

1109.航班预定统计

https://leetcode.cn/problems/corporate-flight-bookings/

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n+1);
        for(vector<int> &booking :bookings)
        {
            ans[booking[0]-1]+=booking[2];
            ans[booking[1]]-=booking[2];
        }
        partial_sum(ans.begin(),ans.end(),ans.begin());
        ans.pop_back();
        return ans;
    }
};

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

相关文章
前缀和、差分、二分
前缀和、差分、二分
73 0
|
5月前
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
58 4
【算法】前缀和与差分
|
7月前
|
算法 C++
c++算法学习笔记 (5)前缀和+差分
c++算法学习笔记 (5)前缀和+差分
|
7月前
|
算法
算法思想总结:前缀和算法
算法思想总结:前缀和算法
|
7月前
|
人工智能 移动开发 算法
算法基础:前缀和与差分
算法基础:前缀和与差分
81 1
算法基础:前缀和与差分
|
7月前
|
存储 人工智能 BI
差分与前缀和
差分与前缀和
45 0
|
7月前
|
人工智能 算法
基础算法--前缀和与差分
基础算法--前缀和与差分
|
存储 人工智能 算法
C++基础算法前缀和和差分篇
C++基础算法前缀和和差分篇
106 0
算法学习--前缀和与差分
算法学习--前缀和与差分
|
算法
基础算法(大数操作 前缀和 差分)
基础算法(大数操作 前缀和 差分)
75 0