Acwing - 算法基础课 - 笔记（四）

冷不防 2023-01-20 06:58 17阅读 0赞

### 文章目录 ###

*   *  数据结构（一）
     *   *  链表
         *  栈和队列
         *   *  单调栈
             *  单调队列
         *  KMP算法

## 数据结构（一） ##

本节讲解的是

1.  链表与邻接表
2.  栈与队列
3.  看毛片（kmp）算法

### 链表 ###

使用数组模拟**单链表**，**双链表**

使用数组模拟的链表，为**静态链表**，对单链表，开2个数组，其中1个用来存每个链表节点的**值**，另1个数组用来存每个节点的**next指针**。

对双链表，开3个数组，其中1个用来存每个链表节点的值，另外2个数组用来存每个节点的**prev**和**next**指针

单链表，用到比较多的是**邻接表**，邻接表经常用来存储**图**和**树**。（会在后续第三章讲图论时带出）

单链表练习题：[Acwing - 826: 单链表][Acwing - 826_]（静态链表）

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int head = -1, idx; // head指针指向第一个节点, idx表示当前用了的下标
    int e[N], ne[N]; // 其中 e 存放链表节点的值, ne 存放链表节点的next指针
    
    // 插入到头节点
    void add_to_head(int x) { 
        e[idx] = x;
        ne[idx] = head; 
        head = idx;
        idx++;
    }
    
    // 删除第k个插入的数后面的数
    void del_after_k(int k) { 
        // 第k个插入的数的下标为k - 1
        if(k == 0) head = ne[head]; // 删除头节点
        else ne[k - 1] = ne[ne[k - 1]];
    }
    
    // 在第k个插入的数后面插入一个
    void add_after_k(int k, int x) { 
        e[idx] = x;
        ne[idx] = ne[k - 1];
        ne[k - 1] = idx;
        idx++;
    }
    
    int main() { 
        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);
            }
        }
        
        //输入完毕, 输出链表
        for(int i = head; i != -1; i = ne[i]) { 
            printf("%d ", e[i]);
        }
        return 0;
    }

双链表练习题：[Acwing - 827: 双链表][Acwing - 827_]

// 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() { 
        // 头节点下标为0, 尾节点下标为1, idx固定从2开始
    	l[0] = -1;
    	r[0] = 1;
    	l[1] = 0;
    	r[1] = -1;
    	idx = 2;
    }
    
    void add(int k, int x) { 
    	// 在下标为k的位置后面, 插入一个数x
    	e[idx] = x;
    	l[idx] = k;
    	r[idx] = r[k];
    	l[r[k]] = idx;
    	r[k] = idx;
    	idx++;
    }
    
    void del(int k) { 
    	// 删除下标为k的数
    	r[l[k]] = r[k];
    	l[r[k]] = l[k];
    }
    
    int main() { 
    	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); // 在链表头插入
    		} else if(op == "R") { 
    			cin >> x;
    			add(l[1], x);
    		} else if(op == "D") { 
    			// 删除第k个插入的数, 第1个插入的数, 下标是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(int i = r[head]; i != 1; i = r[i]) { 
    		printf("%d ", e[i]);
    	}
    	return 0;
    }

// Java
    import java.util.Scanner;
    
    /** * @Author yogurtzzz * @Date 2021/5/8 14:51 **/
    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(int i = r[head]; i != 1; i = r[i]) { 
    			System.out.printf("%d ", e[i]);
    		}
    		System.out.println();
    	}
    }

### 栈和队列 ###

栈，特性是**后进先出**，逻辑上可以理解为只有一个开口的桶，

队列，特性是**先进先出**，逻辑上可以理解为在两端有开口的桶，只能从其中一端插入，另一端取出，就像排队一样，先排队的会先被服务，后排队的后被服务。

这两个数据结构都非常简单，不细说。

数组模拟栈，练习题：[Acwing - 828: 模拟栈][Acwing - 828_]

#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() {  top--; }
    
    int query() {  return stack[top]; }
    
    bool empty() {  return top <= 0; }
    
    int main() { 
    	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;
    }

栈的应用，练习题：[Acwing - 3302: 表达式求值][Acwing - 3302_]

数组模拟队列，练习题：[Acwing - 829: 模拟队列][Acwing - 829_]

#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() {  head++; }
    
    bool empty() {  return head > tail; }
    
    int query() {  return queue[head]; }
    
    int main() { 
    	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;
    }

#### 单调栈 ####

应用场景：给定一个序列，对于序列中的每个数，求解它左边离他最近且比它小的数（或者右边，或者比它大）

比如对于序列`[3, 4, 2, 7, 5]`，求解每个数左边最近的且比它小的数（不存在则返回-1），答案是

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

考虑的方法和双指针类似，先想一下暴力做法，再进行优化

暴力做法就是，先枚举i = 0~n，然后枚举j，j从i-1开始到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]); // 输出
                break; // 跳出循环, 继续对下一个i进行处理
            }
        }
    }

如果采用栈来做的话，就是对于i = 0~n，用一个栈来存i前面所有的数，而我们观察发现，有的数是不会作为答案的。对于 i 前面的数，比如 m 和 n 都小于i ，假设 m < n，则a\[m\]在a\[n\]的左边，如果a\[m\] ≥ a\[n\]，则a\[m\]是不会作为答案输出的。因为i往左寻找，最多找到n这个位置，而a\[n\]要比a\[m\]更小，所以不会再往左找到m。于是，我们只需要保证栈中的元素有单调性即可。

即，若m < n，且a\[m\] >= a\[n\]，则往栈中压入a\[n\]时，会删除先前压入的a\[m\]。最后保证栈中的元素是升序排列的。

而当需要找第i个数的左边最近的且比它小的数时，先将a\[i\]和栈顶元素比较，若栈顶元素≥a\[i\]，则弹出栈顶元素。因为对i后面的数，答案最多取到a\[i\]，所以此时的栈顶对i后面的数是无用的，直接删除。一直删除栈顶元素，直到栈顶元素＜a\[i\]，此时的栈顶就是答案，再把a\[i\]压入栈，继续下一个位置的判断。

练习题：[Acwing - 830: 单调栈][Acwing - 830_]

#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() { 
        top--;
    }
    
    int stack_top() { 
        return stack[top];
    }
    
    bool stack_empty() { 
        return top <= 0; // top == 0 时表示栈为空
    }
    
    int main() { 
        scanf("%d", &n);
        int t;
        for(int i = 0; i < n; i++) { 
            // 无需先读入数组再进行操作
            // 可以同时读入数组并生成答案
            scanf("%d", &t);
            while(!stack_empty()) { 
                int e = stack_top();
                // 当栈非空时, 查看栈顶元素和a[i]的关系
                if(e >= t) stack_pop();
                else { 
                    printf("%d ", e);
                    stack_push(t);
                    break;
                }
            }
            if(stack_empty()) { 
                printf("-1 ");
                stack_push(t);
            }
                
        }
        return 0;
    }

更简短的代码

// 每个元素都只有一次压栈和出栈的机会，所以时间复杂度是O(n)
    #include<iostream>
    using namespace std;
    const int N = 1e5 + 10;
    int stk[N];
    int top;
    
    int main() { 
        int n, t;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) { 
            scanf("%d", &t);
            while(top > 0 && stk[top] >= t) top--; // 保持栈为单调递增
            if(top <= 0) printf("-1 "); // 栈空
            else printf("%d ", stk[top]);
            stk[++top] = t; // 入栈
        }
        return 0;
        
    }

另一道练习题：[Acwing - 131: 直方图中最大的矩形][Acwing - 131_]

核心思路是，对于每个位置的矩形，分别向左向右扩展，找到能扩展的左右边界，所组成的大矩形，就是当前位置的最大矩形。  
假设直方图的下标为i，每个位置的矩形高度为h\[i\]。  
则对于一个位置i，其左边界一定是第一个比h\[i\]高度小的位置，其右边界一定是第一个比h\[i\]小的位置。所以问题就变成了，对于每个i，求解其左侧第一个小于h\[i\]的位置，和其右侧第一个小于h\[i\]的位置。左右边界之间的长度就是这个大矩形的长，而h\[i\]就是大矩形的高。

#include<iostream>
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1e5 + 10;
    
    int a[N], l[N], r[N], stk[N];
    
    
    int main() { 
    	while(true) { 
    		int n;
    		scanf("%d", &n);
    		if(n == 0) break;
    		for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    		// 计算每个位置左侧第一个比其小的
    
    		int top = 0;
    		for(int i = 1; i <= n; i++) { 
    			while(top > 0 && a[stk[top]] >= a[i]) top--;
    			if(top > 0) l[i] = stk[top];
    			else l[i] = 0;
    			stk[++top] = i;
    		}
    
    		// 计算每个位置右侧第一个比其小的
    		top = 0;
    		for(int i = n; i >= 1; i--) { 
    			while(top > 0 && a[stk[top]] >= a[i]) top--;
    			if(top > 0) r[i] = stk[top];
    			else r[i] = n + 1;
    			stk[++top] = i;
    		}
    
    		LL res = 0;
    		for(int i = 1; i <= n; i++) { 
    			int left = l[i] + 1;
    			int right = r[i] - 1;
    			res = max(res, (LL)a[i] * (right - left + 1));
    		}
    		printf("%lld\n", res);
    	}
    	return 0;
    }

#### 单调队列 ####

最经典的应用：求解滑动窗口中的最大值和最小值

也是先想一个暴力的做法，然后考虑一下能删掉那些元素，是否能得到单调性。

练习题：[Acwing - 154: 滑动窗口][Acwing - 154_]

这道题的思路和上面的单调栈思路类似，不再赘述。注意队列里存放的是下标，而不是数组元素的值。这是因为随着窗口的滑动，需要移除左边的元素，此时存放下标会更加方便。

#include<iostream>
    using namespace std;
    
    const int N = 1e6 + 10;
    
    int n, k;
    int a[N], q[N]; // 其中a数组存放原始的数据, q数组用来做单调队列
    
    int main() { 
    	scanf("%d%d", &n, &k);
    	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    	// 找出滑动窗口的最小值
    	int hh = 0, tt = -1; // hh是队头, tt是队尾
    	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--; // 当队尾元素 >= 当前元素时, 移除队尾
    		q[++tt] = i; // 队列里从队头到队尾, 是单调递增的, 队头元素就是当前滑动窗口的最小值
    		if(i >= k - 1) printf("%d ", a[q[hh]]); // 从第k个位置开始, 进行输出
    	}
    	printf("\n");
    
    	// 找出滑动窗口的最大值
    	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--;// 当队尾元素 <= 当前元素时, 移除队尾
    		q[++tt] = i; // 队列里从队头到队尾, 是单调递减的, 队头元素就是当前滑动窗口的最大值
    		if(i >= k - 1) printf("%d ", a[q[hh]]);
    	}
    	return 0;
    }

### KMP算法 ###

时间复杂度O(n)的模式匹配算法。详解可参考我的这篇文章[一文看懂KMP算法][KMP]

练习题：[Acwing - 831 : KMP字符串][Acwing - 831 _ KMP]

#include<iostream>
    using namespace std;
    const int N = 1e5 + 10, M = 1e6 + 10;
    char p[N], s[M];
    int ne[N]; // 针对模式串P的next数组
    int n, m;
    
    int main() { 
        // 字符串的起始下标从1开始, 方便处理边界
        cin >> n >> p + 1 >> m >> s + 1;
        /* 如果用scanf读入的话 scanf("%d", &n); scanf("%s", p + 1); scanf("%d", &m); scanf("%s", s + 1); */
        // 先求解 next 数组
        // 下标从1开始取, next[i] 的值, 表示以 i 为右端点的字串, 最大的前缀和后缀的长度, 这个长度不能超过 i
        // 故 next[1] 的 值不能超过1, 故 next[1] = 0, 从下标 2 开始计算 next数组
        for(int i = 2, j = 0; i <= n; i++) { 
            // 错开一位进行匹配, 每次匹配 i 和 j + 1 位, 第一次则匹配 2 和 1 
            while(j > 0 && p[i] != p[j + 1]) j = ne[j]; // 当前面有匹配上的位时, 看看当前位是否匹配, 若不匹配, 需要回溯 j 
            if(p[i] == p[j + 1]) j++; // 该位匹配上了, 则 j 往后移动一位, 并且当前位置的 next[i] = j;
            ne[i] = j;
        }
        // 求解完毕 next 数组, 开始进行模式匹配
        for(int i = 1, j = 0; i <= m; i++) { 
            while(j > 0 && s[i] != p[j + 1]) j = ne[j]; // 回溯 j
            if(s[i] == p[j + 1]) j++; // 当前位匹配, 后移j
            if(j == n) { 
                // 匹配完成, 开始下一次可能的匹配
                printf("%d ", i - n);
                j = ne[j];
            }
        }
        return 0;
    }

[Acwing - 826_]: https://www.acwing.com/problem/content/828/
[Acwing - 827_]: https://www.acwing.com/problem/content/829/
[Acwing - 828_]: https://www.acwing.com/problem/content/830/
[Acwing - 3302_]: https://www.acwing.com/problem/content/3305/
[Acwing - 829_]: https://www.acwing.com/problem/content/831/
[Acwing - 830_]: https://www.acwing.com/problem/content/832/
[Acwing - 131_]: https://www.acwing.com/problem/content/133/
[Acwing - 154_]: https://www.acwing.com/problem/content/156/
[KMP]: https://blog.csdn.net/vcj1009784814/article/details/116662859
[Acwing - 831 _ KMP]: https://www.acwing.com/problem/content/833/