Basic Algorithm (3)

This video is on two-pointer algorithms, bit operations, discretization, interval merging

Double pointer

  • Two Pointers to different sequences

    Like merge sort

  • Two Pointers to the same sequence

    Like quicksort

To form such as

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        
    }
}
Copy the code

Double-level loops of this kind might be optimized using double-pointers to reduce the time complexity from O(n^2^) to O(n), such as finding the length of the longest continuous, non-repeating subsequence in an array

The most obvious violent solution is to enumerate I = 0 to n, and for each I, treat it as the right endpoint and try to find the furthest left endpoint to its left.

int maxLen = 0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j <= i; j++) {
        // if [j, I] does not contain repeating elements
        if(noRepeat(j, i)) maxLen = max(maxLen, i - j + 1); }}Copy the code

After simple calculation, it can be known that when there are repeated elements in a [j, I] interval, all the numbers after I + 1 as the right endpoint, and the furthest endpoint on the left can be at most j + 1. In other words, as I moves from left to right, the farthest left endpoint of each I, j, can only move from left to right in one direction. Therefore, the double-pointer algorithm can be adopted. The two Pointers I and j only need to go from 0 to N (2n operations) at most to find the answer, and the time complexity is O(n).

int maxLen = 1;
for(int i = 0, j = 0; i < n; i++) {
    while(j <= i && hasRepeat(j, i)) j++;  // If [j, I] contains repeating elements, move j right
    maxLen = max(maxLen, i - j + 1); // Find the longest subsequence with the current I as the right endpoint
}
// The hasRepeat function checks if there are duplicate elements, either using a hash table or opening an array with counting sort
Copy the code

Exercise: ACwing-799: The longest continuous non-repeating subsequence

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int q[N], c[N];  // If the number range is large, or the number is not an integer, we can consider using hash table

int main(a) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    int res = 0;
    for(int i = 0, j = 0; i < n; i++) {
        c[q[i]]++; // move I back one bit, count up one, add q[I] to the set of weights
        while(c[q[i]] > 1) {  // If there is a repeating element in the interval [j, I], only the newly added q[I] can be repeated
            // There is a repeat, j moves one bit to the right
            c[q[j]]--; // remove q[j] from the set of weights
            j++;
        }
        res = max(res, i - j + 1); // For this I, find the farthest left endpoint j
    }
    printf("%d", res);
    return 0;
}
Copy the code

summary

The two-pointer algorithm is usually applicable to the case that there are two levels of loop (the loop variables are I and j respectively). First write a violent solution, and then observe whether there is a monotonic relationship between I and j (that is, if I and J both move in the same direction without looking back). If this monotone relationship exists between I and j, then we can reduce the time complexity from O(n^2^) to O(n) by using double Pointers.

Two-pointer algorithm template

for(int i = 0, j = 0; i < n; i++) {
    while(j < i && check(i, j)) j++;
    // Specific logic
}
Copy the code

An operation

  • Gets the KTH bit of the binary of a number: x >> k & 1

    So we move x to the right by k, and then we do the sum with 1

  • Get the last binary 1 of a number: lowbit(x) = x & -x

    For example, if the binary representation of 10 is 1010, the lowbit operation on 10 yields 10 (binary), which in decimal form is 2

    The lowbit operation is x & -x. Since -x is represented by the complement, it is equal to the inverse of the original code of x plus 1, i.e. -x = ~x + 1

    For example, the binary representation of x is:

    10010, 1000, the inverse of x

    011010111, plus 1

    011011000

    So x & (~ x + 1), the last digit of x, 1, is going to be preserved, and after this position, the two digits are going to be 0’s, and before this position, the two digits are going to be 0’s after the sum operation.

    The simplest use of lowbit: counting the number of 1s in the binary representation of x. This is done by subtracting the result from x each time you perform a Lowbit on x. And you keep going until you get to the point where x is reduced to 0, and you get as many 1’s in x as you subtract.

    Practice: ACwing-801: the number of ones in binary

    #include<iostream>
using namespace std;

const int N = 1e5 + 10;
int n;

int lowbit(int x) {
    return x & -x;
}

int main(a) {
    scanf("%d", &n);
    while(n--) {
        int x;
        scanf("%d", &x);
        int c = 0;
        while(x > 0) {
            x -= lowbit(x);
            c++;
        }
        printf("%d ", c);
    }
    return 0;
}
Copy the code

discretization

Some arrays have large ranges of elements, such as 0, 10^9, but small numbers of elements, such as 1000 elements.

Sometimes (such as the idea of counting sort) we need to operate on the values of the elements as subscripts of the array. It’s impossible to open an array of size 10 to the ninth.

Now we’re mapping these elements to natural numbers starting at 0, or starting at 1. (Also known as sparse array compression)

Examples are as follows

We have an array A, [1, 3, 100, 2000, 500000] (sorted), and we map the elements of this array to

[0, 1, 2, 3, 4], this mapping process is called discretization

There are two main points of discretization:

  • If there are duplicate elements in array A, they may need to be de-duplicated
  • According toa[i], calculate its value after discretization: since the original array has been sorted, binary search can be used here

Discretized code templates

// C++
vector<int> v; // The array to be discretized
sort(v.begin(), v.end()); // Sort the array first
v.erase(unique(v.begin(), v.end()), v.end()); // Deduplicate the array
// map the array values to 0,1,2,3,4,5... Such as natural Numbers

// Find the discretization value of the number
int find(int x) {
    int l = 0, r = v.size() - 1;
    while(l < r) {  // Find the first discretized value greater than or equal to x
        int mid = l + r >> 1;
        if(v[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; If the prefix and difference indices need to start at 1, then increment 1 is required
}
Copy the code

Practice: ACwing-802: Interval sum

// C++, our own solution
// Discretize only the array subscripts involved in the insert operation
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

int index[N], value[N];

void init(vector<pair<int.int>> v) {
    for(int i = 0; i < v.size(); i++) {
        index[i + 1] = v[i].first; Index [I] = index[I] = index[I
        value[i + 1] = value[i] + v[i].second; // Record the cumulative value of this coordinate, construct the prefix and
        // The discretized coordinates start at 1}}int main(a) {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<pair<int.int>> insert;
    while(n--) {
        int x, c;
        scanf("%d%d", &x, &c);
        insert.push_back({x, c});
    }
    sort(insert.begin(), insert.end()); // By default, pairs are sorted in ascending order by first
    / / discretization
    init(insert);
    
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        // If the same position x is inserted many times, x will correspond to multiple continuous coordinates after discretization
        If [5,6] [5,7] represents the position where x=5, add values 6 and 7, then x=5 May correspond to 1 and 2 in the discretized subscripts
        // The first value of the discretized left boundary is >= x
        int ll = 1, lr = insert.size();  / / the left border
        while(ll < lr) {
            int mid = ll + lr >> 1;
            if(index[mid] >= l) lr = mid;
            else ll = mid + 1;
        }
        // Again, because there is no de-weighting, the right boundary here should be the last value <= x
        int rl = 1, rr = insert.size(); / / right border
        while(rl < rr) {
            int mid = rl + rr + 1 >> 1;
            if(index[mid] <= r) rl = mid;
            else rr = mid - 1;
        }
        // Calculate a result
        int res = value[rl] - value[ll - 1];
        // If l and r are at the same position, there may be no value in [l, r]
        // If l <= index[ll] and r >= index[ll], there is no value between [l, r], and the result should be 0
        if(ll == rl && (l > index[ll] || r < index[ll])) res = 0; 
        printf("%d\n", res);
    }
    return 0;
}
Copy the code
// C++, according to the idea of yxc solution
// Discretize all subscripts (all x, l, r)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int.int> PII;

const int N = 3e5 + 10; // The number of subscripts used is n + 2m, of the order of 300,000

vector<PII> add; // Insert operations
vector<PII> query; // Query operations
vector<int> index; // All subscripts to be discretized

int s[N]; // Record the prefix and
int a[N]; / / record values

// Perform discretization
int find(int x) {
    int l = 0, r = index.size() - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if(index[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1; // The discretized subscript starts at 1, because the prefix sum needs to be computed
}

vector<int> : :iterator unique(vector<int> &v) {
    // Remove duplicate elements from an ordered array
    int j = 0;
    for(int i = 0; i < v.size(); i++) {
        if( i == 0|| v[i] ! = v[i -1]) v[j++] = v[i];
    }
    
    // The last position of j is the first position after reweighting
    return v.begin() + j; // 
}

int main(a) {
    int n, m;
    scanf("%d%d", &n, &m);
    // Read all the data
    while(n--) {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});
        index.push_back(x); // Add the subscript to be discretized
    }
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        query.push_back({l, r});
        index.push_back(l);// Add the subscript to be discretized
        index.push_back(r);
    }
    // Discretize all the lower punctuation marks
    sort(index.begin(), index.end()); // sort index first
    index.erase(unique(index), index.end()); // Deduplicate the index array
    
    // Handle inserts
    for(int i = 0; i < add.size(); i++) {
        int p = find(add[i].first); // Find the position to insert (discretized position)
        a[p] += add[i].second; / / insert
    }
    
    // Compute the prefix sum
    for(int i = 1; i <= index.size(); i++) {
        s[i] = s[i - 1] + a[i]; // For all subscripts used, calculate the prefix and
    }
    
    // Process the query
    for(int i = 0; i < query.size(); i++) {
        int l = find(query[i].first);
        int r = find(query[i].second);
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}
Copy the code

The range span is large, but the actual number of numbers used is small, which is suitable for discretization

Practice: Mei Tuan pen test: grid dyeing

Interval merging

Given a number of intervals, if two intervals have an intersection, combine them into one interval

Practice idea:

  1. First sort by the left endpoint of the interval
  2. Then iterate over each interval and merge (similar to the idea of a double pointer)

Practice: ACwing-8023: Interval merging

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int.int> PII;

int main(a) {
    
    int n;
    vector<PII> segments;
    scanf("%d", &n);
    while(n--) {
        int l, r;
        scanf("%d%d", &l, &r);
        segments.push_back({l, r});
    }
    // Data has been read in
    / / sorting
    sort(segments.begin(), segments.end());
    int cnt = 0; // Start counting
    for(int i = 0; i < segments.size(); i++) {
        if(i == segments.size() - 1) {
            // The current interval is the last interval
            cnt++;
            break;
        } else {
            // There is a subsequent interval to merge
            int r = segments[i].second; // The right margin of the current interval
            // Loop merge when there is a subsequent interval
            while(i + 1 < segments.size()) {
                if(segments[i + 1].first > r) break;  // There is no overlap between the latter interval and this interval
                else {
                    // There is an intersection, update the right boundary
                    r = max(r, segments[i + 1].second);
                    i++;
                }
            }
            cnt++; // when the current interval is merged, count + 1}}printf("%d", cnt);
    return 0;
}
Copy the code