acwing基础课 II 数据结构

链表

数组模拟单链表

单链表 格式就是这样吧 e[N] 代表当前点 ne[N] 代表下一代的点.  插入也很简洁.

int ne[N6], idx = 1, e[N6];

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

void insert_head(int x) {
    insert(0, x);
}

void delete_node(int x) {
    ne[x] = ne[ne[x]];
}

int main() {
    int m = read();
    ne[0] = -1;
    char s;
    while (m--) {
        cin >> s;
        int x = read(), y;
        if (s == 'H') insert_head(x);
        else if (s == 'I') y = read(), insert(x, y);
        else if (s == 'D') delete_node(x);
    }
    for (int i = ne[0]; i != -1; i = ne[i]) {
        O(e[i]);
    }
}

数组模拟双链表 ★★★

int idx = 2, e[N5], l[N5], r[N5];
void init() {
    l[1] = 0, r[0] = 1; //这个l0 和 r1真能用到么
}
void insert(int k, int x) {
    e[idx] = x, l[idx] = k, r[idx] = r[k];
    l[r[k]] = idx, r[k] = idx++;
}

void insertHead(int x) {
    insert(0, x);
}
void insertTail(int x) {
    insert(l[1], x);
}
void deleteNode(int x) {
    l[r[x]] = l[x], r[l[x]] = r[x];
}
int main() {
    int m = read();
    char op[10];
    init();

    while (m--) {
        cin >> op; // 这里以后开大一点吧...
        int x = read(), y = 0;
        if (op[0] == 'R') insertTail(x);
        else if (op[0] == 'L') insertHead(x);
        else if (op[0] == 'D') deleteNode(x + 1);
        else if (op[1] == 'R') y = read(), insert(x + 1, y);
        else y = read(), insert(l[x + 1], y);
    }
    for (int i = r[0]; i != 1; i = r[i]) O(e[i]);
    return 0;
}

栈 & 队列 & 单调..

模拟栈

雪菜有的是 从 tt=0 不知道有没有影响.

然后empty() 是 tt>0

注意 stk, 和 tt = -1; ???

int stk[N5], tt = -1; //记住下标是从 -1 开始的
void push(int x) {
    stk[++tt] = x;
}
void pop() {
    --tt;
}
int query() {
    return stk[tt];
}
bool empty() {
    return tt == -1;
}

模拟队列

尾进 头出. tt=-1, hh = 0

int q[N5], tt = -1, hh;
void push(int x) {
    q[++tt] = x;
}
void pop() {
    ++hh;
}
int query() {
    return q[hh];
}
bool empty() {
    return hh > tt;
}

单调栈

输出每个数左边第一个比他小的数. => 单增的栈.

int stk[N6], tt = 0;
int main() {
    int n = read();
    rep(i, 0, n) {
        int x = read();
        while (tt && x <= stk[tt]) tt--;
        O(tt ? stk[tt] : -1);
        stk[++tt] = x;
    }
    return 0;
}

单调队列(双端)

滑动窗口最大值和最小值.

int a[N6], q[N6], tt = -1, hh;
int main() {
    int n = read(), k = read();
    rep(i, 0, n) a[i] = read();
    rep(i, 0, n) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++; // 如果左边不对, 出栈.
        while (hh <= tt && a[q[tt]] >= a[i]) tt--; //最小值, 单增区间
        q[++tt] = i;
        if (i - k + 1 >= 0) O(a[q[hh]]);
    }
    puts("");
    tt = -1, hh = 0;
    rep(i, 0, n) {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--; //最大值, 单减区间
        q[++tt] = i;
        if (i - k + 1 >= 0) O(a[q[hh]]);
    }
    return 0;
}

栈. 表达式求值 ★★★★

不会做... 不过这个顺序..

int stk[N6], tt = 0, top = 0;
char op[N6];

void eval() {
    int y = stk[tt--], x = stk[tt--];
    char c = op[top--];
    if (c == '*') x = x * y;
    else if (c == '/') x = x / y;
    else if (c == '-') x = x - y;
    else if (c == '+') x = x + y;
    stk[++tt] = x;
}
int main() {
    unordered_map<char, int> um = { {'+', 1}, {'-', 1},
        {'*',2},{'/',2} }; // 定义 priority, 小的进栈前大的先完毕
    string equ;
    cin >> equ;
    rep(i, 0, equ.size()) {
        char c = equ[i];
        if (isdigit(c)) {
            int x = 0, j = i;
            while (j < equ.size() && isdigit(equ[j])) {
                x = x * 10 + equ[j++] - '0';
            }
            i = j - 1; // 因为后面要 i ++;
            stk[++tt] = x;
        }
        else {
            if (c == '(') op[++top] = c; // 左括号直接进栈.
            else if (c == ')') {
                while (op[top] != '(') eval();
                //右括号碰到左前一直运算.
                --top;
            }
            else {
                while (top && op[top] != '(' &&
                    um[c] <= um[op[top]]) eval();
                //相同情况就可以eval了
                // 为什么换成 < 不行呢? 
                    // 24 - 5 + 3; 这种 -号需要一定先运算
                op[++top] = c;
            }
        }
    }
    while (top) eval();
    O(stk[tt]);
    return 0;
}

KMP ★★★★

其实也不难 不过像个dp么? 或者正确性挺难证明出来的.

int n, m;
int ne[N5];
char s[N6], p[N5];

int main() {
    cin >> n >> p + 1 >> m >> s + 1; 
    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++; //求next 就是子串和自己匹配.
        ne[i] = j;
    }
    da(ne, n + 2);
    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) {
            O(i - n); j = ne[j];
        }
    }
    return 0;
}

数组元素的目标和

双指针

int a[N5], b[N5];

int main() {
    int n = read(), m = read(), x = read();
    rep(i, 0, n) a[i] = read();
    rep(i, 0, m) b[i] = read();
    int r = m - 1;
    rep(l, 0, n) {
        while (r >= 0 && a[l] + b[r] > x) r--;
        if (a[l] + b[r] == x) {
            O(l), O(r);
            return 0;
        }
    }
    return 0;
}

判断子序列

双指针

int a[N5], b[N5];

int main() {
    int m = read(), n = read();
    int j = 0;
    rep(i, 0, m) b[i] = read();
    rep(i, 0, n) a[i] = read();
    rep(i, 0, n) {
        if (j < m && b[j] == a[i]) j++;
    }
    puts(j == m ? "Yes" : "No");
    return 0;
}

Tire树

Tire 字符串统计

快速 存储字符串集合的数据结构

int son[N5][26], cnt[N5], idx; //idx为0的那个是根 空串 "";
char str[N5];
void insert(char* str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int query(char* str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main() {
    int n = read();
    while (n--) {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

最大异或对.

int a[N5], idx;
int son[N6 * 3][2]; //这里为什么需要 N6*3 个?
void insert(int x) {
    int p = 0;
    per(i, 31, 0) {
        int& s = son[p][x >> i & 1];
        if (!s) s = ++idx;
        p = s;
    }
}
int search(int x) {
    int p = 0, res = 0;
    per(i, 31, 0) {
        int s = x >> i & 1;
        if (son[p][!s]) {
            res += 1 << i; //这里为什么是这样子的...
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}
int main() {
    int n = read();
    rep(i, 0, n)a[i] = read(), insert(a[i]);
    int res = 0;
    rep(i, 0, n) {
        res = max(res, search(a[i]));
    }
    O(res);
    return 0;
}

并查集

合并集合

int p[N5];
int find(int k) {
    if (p[k] != k) p[k] = find(p[k]);
    return p[k];
}
int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1) {
        p[i] = i;
    }
    rep(i, 0, m) {
        char op[2]; scanf("%s", op);
        int l = read(), r = read();
        if (op[0] == 'M') p[find(l)] = find(r);
        else
            puts(find(l) == find(r) ? "Yes" : "No");
    }
    return 0;
}

837. 连通块中点的数量

int p[N5], cnt[N5];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main() {
    int n = read(), m = read();
    rep(i, 1, n + 1) p[i] = i, cnt[i] = 1;
    rep(i, 0, m) {
        char op[4];
        scanf("%s", op);  int l = read();
        if (op[0] == 'C') {
            int r = read();
            l = find(l), r = find(r);
            if (l != r) {
                cnt[l] += cnt[r];
                p[r] = l;
            }
        }
        else if (op[1] == '1') {
            int r = read();
            puts(find(r) == find(l) ? "Yes" : "No");
        }
        else {
            printf("%d\n", cnt[find(l)]);
        }
    }
    return 0;
}

食物链