Find different binary strings with flight booking statistics

This is the 31st day of my participation in the August More Text Challenge

1980. Find different binary strings

Thought analysis

The array is n in length, and each element in the array is a string of length N, which has 2n2^n2n possibilities, representing numbers from 0 to 2n−12^ n-12n −1.

Based on this knowledge, we can convert strings into numbers, store them in a map, and return strings for numbers that do not exist in the first map by iterating through the numbers 0 to 2n−12^ n-12n −1

Alternatively, you can store strings into a map and convert the numbers 0 through 2n−12^ n-12n −1 into strings and compare them with map.

Flight booking statistics

Thought analysis

The easiest way to do this is to add an answer to each bookings[I] request. This will result in O(n2n^2n2) time complexity code.

Try to reduce the time complexity.

This problem has obvious characteristics of region sum and single point query, so we can use difference array to solve this problem, briefly introduce difference, difference can be simply understood as the inverse process of prefix sum, for example, if d[I] is the prefix sum of f[I], then f[I] is the difference of D [I].

If f[I] is [1,2,3,4] then d[I] has [1,3,6,10]. We want the [1,2] of d[I] to increase by 10, then d[I] has [1,13,16,10], then f[I] can be calculated as [1,12,3, -6].

L [I] += v; l[I] += v; L [r + 1] -= v”

(Write the conclusion directly, ghost can understand ah)

So this problem has

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> nums(n);
    for (int i = 0; i < bookings.size(a); i++) { nums[bookings[i][0] - 1] += bookings[i][2];
        if (bookings[i][1] < n) { // There is no need to decrease nums for the last bit, because there are no more numbers left. There is no need to deliberately balance the code for adding regions.
            nums[bookings[i][1]] -= bookings[i][2]; }}for (int i = 1; i < n; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

Copy the code