[Algorithm Training Summer Camp] 7.3 Day Questions—Prefix Sum

Hits: 0

” Algorithm Training Portal

👉Introduction _

learn by heart
🎉✨🎉The only thing I know is that I know nothing 🎉✨🎉

💖 ❄️Our Algorithmic Path❄️💖

=====================================

As we all know, as a qualified programmer,Algorithmic abilityIt is indispensable , and we can always feel the ✨charm✨ of the algorithm in the process of algorithm learning.
              ☀️🌟 Just a few lines of code, condensing the wisdom of countless predecessors; an ordinary loop , that is , the eye for solving
   problems ) , 💝Breadth- First Search (bfs) , 💝Number Theory , 💝Dynamic Programming , etc. There is a long way to go, I will search up and down ! I hope to make progress together with everyone in this training camp and gain something! ! ! 🎉🎉🎉

Today’s Topic: Prefix Sum

👉⭐️first question💎

✨Title _

1. Regions and Retrieval – Arrays are immutable

✨ Ideas :

When NumArray initializes the array, a prefix and array are established, and then the boundary data can be directly obtained from the sum array when querying

✨Code : _

class NumArray {
public:
    vector<int>N;
    vector<int>sum;
    NumArray(vector<int>& nums) {
        N = nums;
        int n = nums.size();
        sum.resize(n);
        sum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        return sum[right] - sum[left] + N[left];
    }
};

👉⭐️Question 2💎

✨Title _

2. Sum of all odd-length subarrays

For each case of odd length Ni, find the sum of all sub-arrays of Ni length (traversing the number of Ni from the first element of the array) in turn and accumulate them

✨Code : _

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

👉⭐️Question 3💎

✨Title _

3. and the same binary subarray

✨ Ideas :

The hash table is used in combination with the prefix sum: the hash table stores the prefix sum, and accumulates when it meets the requirements of the problem

✨Code : _

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
    map<int,int>record;
    record[0]++;
    int sum=0,num=0;
    for(auto i:nums){
        num+=i;
        if(record[num-goal])
        sum+=record[num-goal];  

       record[num]++;
    }
    return sum;
    }
};

👉⭐️Question 4💎

✨Title _

4. Buy a Shovel

There is a shovel that sells for k yuan. There are countless such shovels in the store. You have countless coins of 10 yuan, but you only have one coin of face value r (1<=r<=9). How much do you want to buy at least? Take the shovel, the merchant does not need to give you change

✨Code : _

#include "bits/stdc++.h"
using namespace std;

#define ll long long

#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()

#define            pb                push_back
#define          sz(a)               (int)a.size()


ll query(int l, int r, vector<ll>& p) {
    return p[r] - (l ? p[l - 1] : 0);
}

void solve() {  
    int n, s; cin >> n >> s;
    vector<ll> a(n), p(n);
    forn(i, n) {
        cin >> a[i];
        p[i] = a[i];
        if(i) p[i] += p[i - 1];
    }

    int ans = INT_MAX;

    for(int i = 0; i < n; ++i) {
        int l = i, r = n - 1, pos = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(query(i, mid, p) <= s) {
                pos = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        if(pos == -1 || query(i, pos, p) != s) continue;
        ans = min(ans, n - (pos - i + 1));
    }

    cout << (ans == INT_MAX ? -1 : ans) << "\n";
} 

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

Written at the end :

You may also like...

Leave a Reply

Your email address will not be published.