数据结构

字数统计: 2.3k字   |   阅读时长≈ 11分钟

acwing 算法基础课 数据结构部分

1. 单链表

  • 定义

    1
    int h[N], ne[N], idx, head;

  • 初始化

    1
    2
    idx = 0;
    head = -1;

  • 在头节点插入

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

  • 在第k个(从0开始算的)插入的数后面插入

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

  • 删除第k个插入的数(不包括头节点)

    1
    2
    3
    4
    5
    6
    void remove(int k, int x)
    {
        ne[k] = ne[ne[k]];
    }
    // 头节点
    head = ne[head];

2. 双链表

  • 定义

    1
    int h[N], r[N], l[N], idx;

  • 初始化

    1
    2
    3
    l[1] = 0;
    r[0] = 1;
    idx = 2;

  • 在第k个(其实不是第k个，因为下标是从2开始的，所以其实是k-1)插入的数后面插入一个数

    1
    2
    3
    4
    5
    6
    void add(int k, int x)
    {
        e[idx] = x;
        l[idx] = k, r[idx] = r[k];
       	l[r[k]] = idx, r[k] = idx ++ ;
    }

  • 删除第k个插入的数后面的数

    1
    2
    3
    4
    5
    void remove(int k)
    {
        l[r[k]] = l[k];
        r[l[k]] = r[k];
    }

  • 实现操作

    • 头后面插入

      1
      add(0, x);

    • 尾前面插入

      1
      add(l[1], x);

    • k右边插入

      1
      add(k + 1, x);

    • k左边插入

      1
      add(l[k+1], x);

    • 删除k

      1
      remove(k+1);

3. 栈

  • 定义

    1
    int stk[N], tt = 0;

  • 操作

    1
    2
    3
    4
    5
    6
    7
    8
    // 栈顶
    stk[tt];
    // 弹出
    tt --;
    // 存入
    stk[++tt] = x;
    // 判空
    tt > 0

  • 一个应用，表达式求值

    具体而言：遇到数字直接入数字栈、遇到符号:1. 左括号直接入栈，2.右括号进行计算，直至遇到左括号，3.遇到运算符，如果当前比栈顶运算符优先级小就要计算，直到优先级比栈顶低再入栈

    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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include<iostream>
    #include<stack>
    #include<unordered_map>
    using namespace std;
    stack<int> num;
    stack<char> op;
    void eval()
    {
        int b = num.top(); num.pop();
        int a = num.top(); num.pop();
        char c = op.top(); op.pop();
        int x;
        if(c == '+') x = a + b;
        else if(c == '-') x = a - b;
        else if(c == '*') x = a * b;
        else x = a / b;
        num.push(x);
    }
    int main()
    {
        unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        string s;
        cin >> s;
        for(int i = 0; i < s.size(); i ++ )
        {
            char c = s[i];
            if(isdigit(c))
            {
                int j = i, x = 0;
                while(j < s.size() && isdigit(s[j])) x = x * 10 + s[j++] - '0';
                i = j - 1;
                num.push(x);
            }
            else if(c == '(') op.push(c);
            else if(c == ')')
            {
                while(op.size() && op.top() != '(')
                    eval();
                op.pop();
            }
            else
            {
                while(op.size() && pr[c] <= pr[op.top()]) eval();
                op.push(c);
            }
        }
        while(op.size()) eval();
        cout << num.top() << endl;
        return 0;
    }

4. 队列

  • 定义

    1
    int q[N], hh, tt = -1;

  • 操作

    1
    2
    3
    4
    5
    6
    7
    8
    // 入队列
    q[++tt] = x;
    // 队头
    q[hh];
    // 出队列
    hh++;
    // 判空
    hh <= tt

5. 单调栈

单调栈指的是在维护栈的过程中保持栈中元素是单调的，据此可以解决求解某个元素左边第一个比它小的元素之类的问题。

模板

1
2
3
4
5
6
7
8
9
for(int i = 0; i < n; i ++ )
{
    int x;
    cin >> x;
    while(tt&&stk[tt] >= x) tt--;
    if(tt) cout << stk[tt] << ' ';
    else cout << -1 << ' ';
    stk[++tt] = x;
}

6. 单调队列

单调队列指的是队列中的元素是单调的，据此可以解决滑动窗口中的最值问题

模板

1
2
3
4
5
6
7
for(int i = 0; i < n; i ++ )
{
    if(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]] << ' ';
}

7. KMP 算法

字符串匹配算法

对于匹配过程：

从前往后匹配，直到字符串的第i位和模式串的第j+1位不匹配，此时需要将模式串的j指针回溯，回溯的规则是 模式串的前j位的最长前后缀相同的位置，此时能保证新的j+1之前的都是匹配上的。如果第j+1位依然不匹配，则需要继续回溯，直到退无可退了。

1
2
3
4
5
6
7
8
9
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)
    {
        // 成功匹配上了
	}
}

对于ne数组的求解：

由前面的匹配过程可以看出，我们需要对模式串做预处理，也就是求出成功匹配i位时，第i+1位不匹配时，应该回溯多少位，需要回溯的长度就等于(对前i位而言，最长的前缀与后缀匹配长度)，这个匹配过程可以理解位自己和自己匹配。

i = 1 时，肯定是无需回溯的，所以ne[1] = 0即可，即退到了1则肯定不用回退了，直接往后移动一位即可。

1
2
3
4
5
6
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;
}

8. 字典树

字典树，前缀树，Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 插入树中
void add(string s)
{
    int p = 0;
    for(auto& c: s)
    {
        int x = c - 'a';
        if(!son[p][x]) son[p][x] = ++idx;
        p = son[p][x];
	}
    cnt[p] ++;
}
// 查找
int find(string s)
{
    int p = 0;
    for(auto& c : s)
    {
        int x = c - 'a';
        if(!son[p][x]) return 0;
        p = son[p][x];
	}
    return cnt[p];
}

字典树也并非只可以处理字符串，还可以处理其他各种形式的数据

9. 并查集

可以在近乎$O(1)$的时间内完成两个集合的合并以及判别两个元素是否属于同一个集合

1
2
3
4
5
6
// 带路径压缩的查找函数
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

10. 堆

动态维护一堆数据中的最值，是一棵完全二叉树

核心操作就两个:

  • down:

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

  • up:

    1
    2
    3
    4
    5
    6
    7
    8
    void up(int u)
    {
        while(u / 2 && h[u / 2] > h[u])
        {
            heap_swap(u, u / 2);
            u /= 2;
    	}
    }
    1
    2
    3
    4
    5
    6
    7
    // heap_swap   ph[i] 指的是第i个插入的数在第几个下标, hp[i] 指的是第i个下标对应的是第几个插入的数
    void heap_swap(int a, int b)
    {
        swap(ph[hp[a]], ph[hp[b]]);
        swap(hp[a], hp[b]);
        swap(h[a], h[b]);
    }

据此组合出的操作:

  • 初始化

    1
    2
    3
    int h[N], ph[N], hp[N];
    int m = 0, sz = 0; // m为记录一下现在是第几个插入的，sz记录的是堆的size
    for(int i = n / 2; i ; i -- ) down(i); // 完全二叉树的性质， n/2是第一个非叶子节点

  • 入堆

    1
    2
    3
    4
    m ++ , sz ++ ;
    ph[m] = sz, hp[sz] = m;
    h[sz] = x;
    up(sz);

  • 出堆

    1
    2
    heap_swap(1, sz -- );
    down(1);

  • 堆顶

    1
    h[1];

  • 修改第k个插入的元素

    1
    2
    3
    k = ph[k];
    h[k] = x;
    up(k), down(k);

  • 删除第k个插入的元素

    1
    2
    3
    k = ph[k];
    h[k] = x;
    up(k), down(k);

11. 哈希表

在$O(1)$的时间复杂度内完成增删改查

  • 拉链法 : 开的长度和数据长度差不多长就可以了，$N$为远离2的次幂的质数时可以有效降低冲突概率

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int h[N], e[N], ne[N], idx;
    void add(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = h[k], ne[idx] = h[k], h[k] = idx ++ ;
    }
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for(int i = h[k]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(j == x) return true;
    	}
        return false;
    }

  • 开放寻址法: 开的数组长度比数据长度大一到两倍即可，$N$为远离2的次幂的质数时可以有效降低冲突概率

    开放寻址法找的是一个位置，如果是查找就是可能出现的位置，如果是插入就是插入的位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int find(int x)
    {
        int k = (x % N + N) % 3;
        while(h[k] != 0x3f3f3f3f && h[k] != x)
        {
            k ++ ;
            if(k == N) k = 0;
    	}
        return k;
    }

    上述代码中，给定一个$x$，先算出它的hash值$k$，然后就判定这个位置是不是空的，如果是空的，说明没出现过x，那么是插入操作的话，就要把$x$插入到这里，如果是查找操作的话，就是找不到。如果这个位置不是空的，说明被占用了，$x$可能是插入到后面去了，所以一直往后面找，直到为空为止，因为这个位置还没找打的话，说明$x$确实没出现过，插入的话就把$x$插入到这里，查找的话就是没出现过。

12. 字符串哈希

给字符串的Hash函数

字符串Hash是一个前缀函数，可以定义为

$H(i) = (p^{i-1} s_1 + p^{i-2}s_2 + … + p^1s_{i-1} + p^0s_i) mod(M)$

一般，取$P = 131$ 或者$P = 13331$，$M = 2^{64}$,此时发生冲突的概率最低

要求取中间一段字符串的hash值，可以这么求

$H[l,r] = (H(r) - H(l-1) *p^{r - l + 1}) mod(M)$

下面是判断一个字符串中的两段是否相同的算法，$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
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
const int N = 100010;
const int P = 131;
typedef unsigned long long ULL;
ULL h[N], p[N];
ULL get(int l, int r)
{
    return h[r] - h[l-1] * p[r - l + 1];
}
int main()
{
    int n, m;
    cin >> n >> m;
    p[0] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        char c;
        cin >> c;
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + c - 'a';
    }
    while(m -- )
    {
        int a,b,x,y;
        cin >> a >> b >> x >> y;
        if(get(a, b) == get(x, y)) puts("Yes");
        else puts("No");
    }
    return 0;
}
  • © 2019-2022 Wendell
  • Powered by Hexo Theme Ayer

请我喝杯咖啡吧~

支付宝
微信