Acwing – Fundamentals of Algorithms – Notes (4)

Data Structure (1)

This section is about

1. Linked lists and adjacency lists
2. The stack and queue
3. Watch porn (KMP) algorithm

The list

Use arrays to simulate single linked lists, double linked lists

The linked list simulated by array is a static linked list. For a single linked list, two arrays are opened, one of which is used to store the value of each linked list node, and the other array is used to store the next pointer of each node.

For double-linked lists, open three arrays, one for the value of each linked list node, and two for the prev and next Pointers for each node

Adjacency lists are often used to store graphs and trees. (This will be covered in chapter 3 of graph theory.)

Acwing-826: Single Linked List (Static Linked List)

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int head = - 1, idx; // the head pointer points to the first node, and idx indicates the current subscript
int e[N], ne[N]; E stores the value of the linked list node, ne stores the next pointer to the linked list node

// Insert the first node
void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head; 
    head = idx;
    idx++;
}

// Delete the number after the KTH inserted number
void del_after_k(int k) {
    // The index of the KTH insertion is k-1
    if(k == 0) head = ne[head]; // Delete the header node
    else ne[k - 1] = ne[ne[k - 1]];
}

// Insert one after the KTH number
void add_after_k(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k - 1];
    ne[k - 1] = idx;
    idx++;
}

int main(a) {
    int m;
    cin >> m;
    while(m--) {
        char op;
        cin >> op;
        if(op == 'H') {
            int x;
            cin >> x;
            add_to_head(x);
        } else if(op == 'D') {
            int k;
            cin >> k;
            del_after_k(k);
        } else if(op == 'I') {
            int k, x;
            cin>> k >> x; add_after_k(k, x); }}// Output the linked list
    for(inti = head; i ! =- 1; i = ne[i]) {
        printf("%d ", e[i]);
    }
    return 0;
}
Copy the code

Double linked list Exercise: ACwing-827: Double linked list

// C++
#include<iostream>
#include<string>
using namespace std;

const int N = 1e5 + 10;

int l[N], r[N], e[N], idx, head = 0, tail = 1;

void init(a) {
    // The header node is subscript 0, the tail node is subscript 1, and the idx is fixed at 2
	l[0] = - 1;
	r[0] = 1;
	l[1] = 0;
	r[1] = - 1;
	idx = 2;
}

void add(int k, int x) {
	// Insert a number x after k
	e[idx] = x;
	l[idx] = k;
	r[idx] = r[k];
	l[r[k]] = idx;
	r[k] = idx;
	idx++;
}

void del(int k) {
	// Delete the number subscript k
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

int main(a) {
	init();
	int m;
	cin >> m;
	for(int i = 0; i < m; i++){
		string op;
		cin >> op;
		int k, x;
		if(op == "L") {
			cin >> x;
			add(0, x); // Insert in the list header
		} else if(op == "R") {
			cin >> x;
			add(l[1], x);
		} else if(op == "D") {
			// Delete the KTH insert, the first insert, subscript 2
			cin >> k;
			del(k + 1);
		} else if(op == "IL") {
			cin >> k >> x;
			add(l[k + 1], x);
		} else if(op == "IR") {
			cin >> k >> x;
			add(k + 1, x); }}for(inti = r[head]; i ! =1; i = r[i]) {
		printf("%d ", e[i]);
	}
	return 0;
}
Copy the code

// Java
import java.util.Scanner;

/ * * *@Author yogurtzzz
 * @Date2021/5/8 nothing * * /
public class Main {

	static int[] l, r, e;
	static int head = 0, tail = 1, idx = 0;

	static void init(int n) {
		l = new int[n + 10];
		r = new int[n + 10];
		e = new int[n + 10];
		l[0] = -1;
		r[0] = 1;
		l[1] = 0;
		r[1] = -1;
		idx = 2;
	}

	static void add(int k, int x) {
		e[idx] = x;
		l[idx] = k;
		r[idx] = r[k];
		l[r[k]] = idx;
		r[k] = idx;
		idx++;
	}

	static void del(int k) {
		r[l[k]] = r[k];
		l[r[k]] = l[k];
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		init(n);
		while(n-- > 0) {
			String op = scanner.next();
			if ("L".equals(op)) {
				int x = scanner.nextInt();
				add(0, x);
			} else if ("R".equals(op)) {
				int x = scanner.nextInt();
				add(l[1], x);
			} else if ("D".equals(op)) {
				int k = scanner.nextInt();
				del(k + 1);
			} else if ("IL".equals(op)) {
				int k = scanner.nextInt(), x = scanner.nextInt();
				add(l[k + 1], x);
			} else if ("IR".equals(op)) {
				int k = scanner.nextInt(), x = scanner.nextInt();
				add(k + 1, x); }}for(inti = r[head]; i ! =1; i = r[i]) {
			System.out.printf("%d ", e[i]); } System.out.println(); }}Copy the code

The stack and queue

Stack, which features last in, first out, can be logically understood as a bucket with only one opening,

A queue is a first-in, first-out bucket. It can be logically understood as a bucket with openings at both ends. It can only be inserted at one end and taken out at the other end.

Both data structures are very simple, without going into detail.

Array simulation stack exercise: ACwing-828: simulation stack

#include<iostream>
#include<string>
using namespace std;

const int N = 1e5 + 10;
int stack[N];
int top;

void push(int x) { stack[++top] = x; }

void pop(a) { top--; }

int query(a) { return stack[top]; }

bool empty(a) { return top <= 0; }

int main(a) {
	int n, x;
	cin >> n;
	while(n--) {
		string op;
		cin >> op;
		if(op == "push") {
			cin >> x;
			push(x);
		} else if(op == "pop") {
			pop();
		} else if(op == "empty") {
			if(empty()) printf("YES\n");
			else printf("NO\n");
		} else if(op == "query") {
			printf("%d\n", query()); }}return 0;
}
Copy the code

Stack application, exercise: ACwing-3302: Expression evaluation

Acwing-829: Array simulation queue

#include<iostream>
#include<string>
using namespace std;

const int N = 1e5 + 10;
int queue[N];
int head = 0, tail = - 1;

void push(int x) { queue[++tail] = x; }

void pop(a) { head++; }

bool empty(a) { return head > tail; }

int query(a) { return queue[head]; }

int main(a) {
	int n, x;
	cin >> n;
	while(n--) {
		string op;
		cin >> op;
		if(op == "push") {
			cin >> x;
			push(x);
		} else if(op == "pop") {
			pop();
		} else if(op == "empty") {
			if(empty()) printf("YES\n");
			else printf("NO\n");
		} else if(op == "query") {
			printf("%d\n", query()); }}return 0;
}
Copy the code

Monotonous stack

Application Scenario: Given a sequence, for each number in the sequence, find the nearest and smaller number to its left (or to the right, or larger).

For example, for the sequence [3, 4, 2, 7, 5], find the nearest and smaller number to the left of each number (return -1 if none exists), and the answer is

[-1, 3, -1, 2, 2]

The way to think about it is similar to the two-pointer, think about violence first, and then optimize

To do this, enumerate I = 0 to n, and then enumerate j, starting from i-1 to 0

int a[n] = {3.4.2.7.5};
for(int i = 0; i < n; i++) {
    for(int j = i - 1; j >= 0; j--) {
        if(a[i] > a[j]) {
            printf("%d ", a[j]); / / output
            break; // Break out of the loop and proceed to the next I}}}Copy the code

If we use a stack to do it, that is, for I = 0 to n, we use a stack to store all the numbers before I, and we observe that some numbers will not be the answer. For numbers before I, such as m and n both less than I, if m < n, then a[m] is to the left of a[n]. If a[m] ≥ a[n], then a[m] is not printed as the answer. Because I looks to the left, I can find at most n, and A [n] is smaller than a[m], so I can’t find m any further to the left. So, we just need to keep the elements on the stack monotonic.

That is, if m < n and a[m] >= a[n], the a[m] previously pushed will be deleted when a[n] is pushed to the stack. Finally, ensure that the elements in the stack are sorted in ascending order.

To find the nearest and smaller number to the left of the ith number, compare a[I] with the top element first. If the top element is ≥ A [I], the top element is popped. The top of the stack is useless for the number after I, because the answer to the number after I is at most a[I]. Delete the top element until the top element < a[I], at which point the top of the stack is the answer, and then push a[I] onto the stack to continue the judgment of the next position.

Exercise: ACwing-830: Monotonous stack

#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int stack[N];
int n, top;

void stack_push(int x) {
    stack[++top] = x;
}

void stack_pop(a) {
    top--;
}

int stack_top(a) {
    return stack[top];
}

bool stack_empty(a) {
    return top <= 0; // If top == 0, the stack is empty
}

int main(a) {
    scanf("%d", &n);
    int t;
    for(int i = 0; i < n; i++) {
        // There is no need to read the array before operating
        // You can read the array and generate the answer at the same time
        scanf("%d", &t);
        while(! stack_empty()) {int e = stack_top();
            // Check the relationship between a[I] and the top element of the stack when the stack is not empty
            if(e >= t) stack_pop();
            else {
                printf("%d ", e);
                stack_push(t);
                break; }}if(stack_empty()) {
            printf("1"); stack_push(t); }}return 0;
}
Copy the code

Shorter code

// Each element has only one push and exit, so the time complexity is O(n).
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, tt;  // tt represents the top position of the stack
int stk[N]; // STK [] arrays are used to simulate stacks

int main(a) {
    scanf("%d", &n);
    int x;
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        while(tt && stk[tt] >= x) tt--; // If the stack is not empty and the top element is greater than a[I], pop the top element of the stack
        // At the end of the loop, the stack is either empty or the top element is the answer
        if(tt) printf("%d ", stk[tt]); // If the stack is not empty, output the top element of the stack
        else printf("1");
        stk[++tt] = x; // Push the current element onto the stack
    }
    return 0;
}
Copy the code

The monotonous queue

The most classic application: solving the maximum and minimum values in sliding Windows

Again, think of a violent way to do it, and then see if you can get rid of those elements and see if you can get monotonicity.

Acwing-154: Sliding Windows

The idea of this problem is similar to the monotonous stack idea above, and will not be repeated. Note that the queue stores subscripts, not the values of array elements. This is because as the window slides, the left element needs to be removed, making it easier to store subscripts.

#include<iostream>
using namespace std;

const int N = 1e6 + 10;

int n, k;
int a[N], q[N]; // Array A is used to store raw data, and array Q is used as monotonic queue

int main(a) {
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);

	// Find the minimum value of the sliding window
	int hh = 0, tt = - 1; // hh is the head of the team, tt is the tail of the team
	for(int i = 0; i < n; i++) {
		// If the queue is not empty and the head subscript is to the left of the sliding window's left boundary, remove the queue head
		while(hh <= tt && q[hh] < i - k + 1) hh++;
		while(hh <= tt && a[q[tt]] >= a[i]) tt--; // Remove the end of the queue when the end element >= the current element
		q[++tt] = i; // The queue is monotonically increasing from the head of the queue to the end of the queue. The head element is the minimum value of the current sliding window
		if(i >= k - 1) printf("%d ", a[q[hh]]); // Start at position k and output
	}
	printf("\n");

	// Find the maximum sliding window
	hh = 0, tt = - 1;
	for(int i = 0; i < n; i++) {
		while(hh <= tt && q[hh] < i - k + 1) hh++;
		while(hh <= tt && a[q[tt]] <= a[i]) tt--;// When the end element <= current element, remove the end of the queue
		q[++tt] = i; // There is a monotonically descending queue from the head of the queue to the end of the queue, and the head element is the current maximum sliding window
		if(i >= k - 1) printf("%d ", a[q[hh]]);
	}
	return 0;
}
Copy the code

KMP algorithm

Time complexity O(n) pattern matching algorithm. Detailed explanation can refer to my article to understand the KMP algorithm

Practice: ACwing-831: KMP string

#include<iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int ne[N]; // Next array for pattern string P
int n, m;

int main(a) {
    // The initial subscript of the string starts at 1 to facilitate boundary handling
    cin >> n >> p + 1 >> m >> s + 1;
    // Start with the next array
    // Next [I], starting at 1, is the value of next[I], indicating the length of the prefix and suffix, which cannot exceed I
    // Next [1] cannot exceed 1, so next[1] = 0, starting with subscript 2
    for(int i = 2, j = 0; i <= n; i++) {
        // Stagger one bit for matching, each time matching I and j + 1 bit, the first time matching 2 and 1
        while(j > 0&& p[i] ! = p[j +1]) j = ne[j]; // If there is a matching bit on the front, check whether the current bit matches, if not, need to backtrack j
        if(p[i] == p[j + 1]) j++; // next[I] = next;
        ne[i] = j;
    }
    // Complete the next array and start the pattern matching
    for(int i = 1, j = 0; i <= m; i++) {
        while(j > 0&& s[i] ! = p[j +1]) j = ne[j]; / / back j
        if(s[i] == p[j + 1]) j++; // The current bit matches
        if(j == n) {
            // When the match is complete, start the next possible match
            printf("%d ", i - n); j = ne[j]; }}return 0;
}
Copy the code