AcWing 数据结构章节笔记

这一章的重点，是把常见结构写成稳定模板，并知道题目到底在考“结构操作”还是“结构思想”。

本章核心模板

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int head = -1, idx = 0;
int e[N], ne[N];

void add_to_head(int x) {
    e[idx] = x, ne[idx] = head, head = idx++;
}

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

void remove(int k) {
    ne[k] = ne[ne[k]];
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int e[N], l[N], r[N], idx;

void init() {
    r[0] = 1, l[1] = 0, idx = 2;
}

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

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

单调栈 / 单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 单调栈：找左边最近比它小的数
for (int i = 0; i < n; i++) {
    while (tt && stk[tt] >= a[i]) tt--;
    if (!tt) cout << -1 << ' ';
    else cout << stk[tt] << ' ';
    stk[++tt] = a[i];
}

// 单调队列：滑动窗口最小值
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) cout << a[q[hh]] << ' ';
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 2, j = 0; i <= n; 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) {
        cout << i - n << ' ';
        j = ne[j];
    }
}

Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int son[N][26], cnt[N], idx;

void insert(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(string s) {
    int p = 0;
    for (char c : s) {
        int u = c - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int p[N], sz[N];

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a != b) {
        p[a] = b;
        sz[b] += sz[a];
    }
}

堆

1
2
3
4
5
6
7
8
9
void down(int u) {
    int t = u;
    if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t) {
        swap(h[u], h[t]);
        down(t);
    }
}

本章题目与题解要点

单链表 / 双链表

  • 826 单链表：静态数组模拟链表，重点是下标和 head 的更新顺序。
  • 827 双链表：双向指针都要维护，删除节点时左右两边都要改。

栈 / 队列

单调栈 / 单调队列

  • 830 单调栈：找每个数左边第一个比它小的数。
  • 154 滑动窗口：经典单调队列模板题，同时输出窗口最小值和最大值。

KMP

  • 831 KMP字符串：先求模式串 next 数组，再在线性时间里匹配文本串。

Trie

并查集

堆

  • 838 堆排序：建堆后连续取最小值。
  • 839 模拟堆：要支持删除任意插入点和修改，需要额外维护映射数组。

哈希表

这一章怎么复习

  1. 手写 826、827、836 三个模板。
  2. 再做 830 和 154，确认单调结构已经熟悉。
  3. 最后看 240、839、143，这三题是本章区分度比较高的题。

返回导航