【五月集训5.8】———前缀和

开更五月集训专题，由浅入深，深入浅出，飞向大厂！

六作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min

• ☘前言☘
• 1480. 一维数组的动态和
• • 解题思路
  • 代码
  • 注意的点
• 1588. 所有奇数长度子数组的和
• • 解题思路
  • 代码
  • 注意的点
• 1442. 形成两个异或相等数组的三元组数目
• • 解题思路
  • 代码
  • 注意的点
• 1094. 拼车
• • 解题思路
  • 代码
  • 注意的点
• 写在最后

1480. 一维数组的动态和

直接计算就好了。

class Solution {
public:
    vector runningSum(vector& nums) {
        int n = nums.size();
        for(int i = 1;i < n;++i)    nums[i] += nums[i -1];
        return nums;
    }
};

没啥

1588. 所有奇数长度子数组的和

比上面的更进一步

class Solution {
public:
    int sumOddLengthSubarrays(vector& arr) {
        int n = arr.size(),ans = 0;
        for(int i = 1;i < n;++i)    arr[i] += arr[i -1];
        for(int i = 1;i <= n;i += 2){
            ans += arr[i - 1];
            for(int  j = 1;j + i <= n;++j)
                ans += arr[j + i - 1] - arr[j - 1]; 
        }
        return ans;
    }
};

我这都快纯c了。。。。

1442. 形成两个异或相等数组的三元组数目

直接求前缀异或和就好了。

class Solution {
public:
    int countTriplets(vector& arr) {
        int n = arr.size(),ans = 0;
        for(int i = 1;i < n;++i)    arr[i] ^= arr[i-1];
        unordered_map Maps;
        for(int j = 1;j < n;++j){
            Maps.clear();
            ++Maps[arr[j - 1]];//i == 0
            for(int i = 1;i < j;++i)    ++Maps[arr[j - 1] ^ arr[i - 1]];
            for(int k = j;k < n;++k)
                ans+= Maps[arr[k] ^ arr[j - 1]];
        }
        return ans;
    }
};

三维枚举可以用j做划分，然后用hash表加速。

1094. 拼车

根据每个时刻的人数统计出来，不超过座位的个数就是可以的，否则返回false。

class Solution { 
public:
    bool carPooling(vector>& trips, int capacity) {
        vector nownum(1002);
        int sum = 0;
        for(auto trip : trips)
            nownum[trip[2]] -= trip[0],nownum[trip[1]] += trip[0];
        for(int i = 0;i < 1001;i++){
            sum += nownum[i];
            if(sum > capacity)  return false;
        }
        return true;
    }
};

1. C++的好多操作还是不是很熟悉。

周赛炸了，水墨屏烧完了，考试快要开始了，心态爆炸ing-。-