1 链表与邻接表

1
2
3
4
5

struct Node{
    int val;
    Node *next;
}
new Node();

1.1 用数组模拟链表

  • 用数组模拟单链表(静态链表): 邻接表(存储图和树)
    • O(1)时间找下一个点, O(n)时间找上一个点
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;

const int N = 100010; 
int head, e[N], ne[N], idx;

void init(){
    head = -1;
}
void add_to_head(int x){
    ne[idx] = head;
    head = idx;
    e[idx] = x;
    idx ++;
}
void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}
void del(int k){
    ne[k] = ne[ne[k]];
}

1.2 用数组模拟双链表

  • 每个节点有两个指针, 指向前后 l[N], r[N], 0对应head, 1对应tail, 两个边界不包含实质内容
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
using namespace std;

const int N = 100010; 
int head, e[N], l[N], r[N], idx;

void init(){
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
void add(int k, int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
} 
void del(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

2 栈与队列

2.1 模拟栈

1
2
3
4
5
6
7

int stk[N], tt;
// 插入
stk[ ++t] = x;
// 弹出
t -- ;
//判断是否为空
return t > 0; // 不空

2.2 单调栈

  • 求每一个数左边离它最近且比它小的数, 没有返回-1
  • 事实上对于这样的要求, 只需要保留单调上升序列即可, 逆序对的第一个元素删掉
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
using namespace std;

const int N = 100010;
int n;
int stk[N], tt;
int main(){
    ios::sync_with_stdio(false);
    
    scanf("%d", &n);
    for (int i=0; i<n; i++){
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) t --;
        if (tt) printf("%d ", stk[tt]);
        else printf("-1 ");
        
        stk[ ++t] = x;
    }
    return 0;
}

2.3 滑动窗口里的最大值和最小值 (单调队列)

  • 在找最小值时, 只要前面的元素比后面的元素大, 那么大的元素一定没有用
  • 找最大值是完全对称的写法

3 kmp

  • 暴力怎么做
  • 如何优化
    • next[i] = j表示p[1,…,j] = p[i-j+1,…,i]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
using namespace std;

const int N = 10010, M=100010;
int n, m;
int p[N], s[M];
int ne[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    // 求next过程
    for (int i=2, j=0; i<=m; i++){
        while (j && p[i] != p[j+1]) j = ne[j];
        if (p[i] == p[j+1]) j ++;
        ne[i] = j;
    }
    // 匹配过程
    for (int i=1, j=0; i<=m; i++){
        while (j && s[i] != p[j+1]) j = ne[j];
        if (s[i] != p[j+1]) j ++;
        if (j == n){
            // 匹配成功
        }
    }
}