算法备忘录·数据结构

本文最后更新于 2022年11月21日 晚上

一直以来，没能系统学习算法，是我心中的痛；现在学了 y 总的算法基础课，做做笔记，希望能够有所收获。
这是第二节，数据结构。

数据结构

链表

  • 通常情况，动态链表的速度较慢。这往往难以满足算法题的要求，因此使用数组来静态的表示链表。

单链表

  • 模板

    • head 储存链表头（直接记录了第一个节点的位置），e[] 存储节点的值，ne[] 存储节点指向的下一个节点位置，idx 表示当前用到哪个节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 初始化
    void init(){
        head = -1; // -1 表示指向空集
        idx = 0;
    }

    //  在链表头插入一个数 a，注意是先新节点指向下一个，再表头指向新节点
    void insert(int a){
        e[idx] = a, ne[idx] = head, head = idx, idx ++;
    }

    // 删除头节点，需要保证头节点存在
    void remove(){
        head = ne[head];
    }

双链表

  • 模板

    • e[] 存储节点的值，l[] 存储节点指向的上一个节点位置，r[] 存储节点指向的下一个节点位置，idx 表示当前用到哪个节点。设 0 是左端点， 1 是右端点，因此 idx 从 2 开始。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 初始化
    void init(){
        r[0] = 1, l[1] = 0;
        idx = 2;
    }

    //  在节点 a 的右边插入数 x
    void insert(int a, int x){
        e[idx] = x;
        l[idx] = a, r[idx] = r[a];
        l[r[a]] = idx, r[a] = idx;
        idx ++;
    }

    // 删除节点 a
    void remove(int a){
        l[r[a]] = l[a];
        r[l[a]] = r[a];
    }

栈、队列

栈

  • FILO

  • 模板

    • 设栈顶初始为 0，表示空， tt 总指向栈顶元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // tt 表示栈顶
    int stk[tt], tt = 0;

    // 向栈顶插入一个数
    stk[++ tt] = x;

    // 栈顶弹出一个数
    tt --;

    // 栈顶的值
    stk[tt];

    // 判断栈是否为空
    if (tt > 0){

    }

队列

  • FIFO

普通队列

  • 模板

    • 设队头初始为 1，队尾初始为 -1，表示空，tt 总指向队尾元素
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int q[N], hh = 0, tt = -1;

    // 向队尾插入一个数
    q[++ tt] = x;

    // 从队头弹出一个数
    hh ++；

    // 队头的值
    q[tt];

    // 判断队列是否为空
    if (hh <= tt){

    }

循环队列

  • 模板

    • 设队头初始为 0，队尾初始为 0，表示空，tt 总指向队尾元素的后一个位置——因为如果按照普通队列那样初始化，队尾就到了 N−1N-1 处
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    int q[N], hh = 0, tt = 0;

    // 向队尾插入一个数
    q[tt ++] = x;
    if (tt == N) tt = 0;

    // 从队头弹出一个数
    hh ++;
    if (hh == N) hh = 0;

    //队头的值
    q[hh];

    //判断队列是否为空
    if (hh != tt){

    }

单调栈

  • 满足单调性的栈结构，插入时要维护其单调性

  • 常见模型：找出每个数这边离它最近的比它大/小的数

  • 模板（插入）

    1
    2
    3
    4
    5
    int tt = 0;
    for (int i = 0; i < n; i ++){
        while (tt && check(stk[tt],i)) tt --;
        stk[++ tt] = i;
    }

单调队列

  • 满足单调性的队列结构，队尾插入要维护其单调性

  • 常见模型：找出滑动窗口中的最大值/最小值

  • 模版（插入）

    1
    2
    3
    4
    5
    6
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++){
        while (hh <= tt && check_out(q[hh])) hh ++; // 判断队头是否在滑动窗口中
        while (hh <= tt && check(q[tt], i)) tt--; // 这里和单调栈一样
        q[++ tt] = i;
    }

KMP

  • 问题：模板串 pp 在 模式串 ss 中 的匹配

  • KMP 算法的思路

    • 每次失配时，不是像暴力那样把模板串 pp 往后移动一位，而是把 pp 串向后移动多位。这里的移动位数对应的是找到长度最长的相等前缀串，所以可以一次移动多位了。
    • 对于每个模板串的字符，如果失配时，应该具体移动多少位呢？定义 next[] 数组来存模式串中每个前缀最长能够匹配前缀字符串的字符的下标。——我们发现相等前缀串是和模式串无关的

  • 如何求 next[] ？

    • 首先看 pp 在 ss 中是如何匹配的。设 pp 和 ss 的起始下标均为 1，j 指向 pp 已经在 ss 中匹配的部分（因此，初始 j = 0）。如果j+1位无法匹配，那么就移动位数，使 j = ne[j]。继续以上操作，如果能够匹配就比较下一位，相应的j ++。
      • 由于初始下标为 1，用 string 类型输入是不行的。可以开两个char[]，然后 cin >> p + 1 >> s + 1。
    • 接下来，考虑求 next[]。事实上两个串之间匹配是相互的，因为模板串移动匹配模式串也可以看成模式串移动匹配模板串。所以，我们求 ne[i] 时，相当于每次用模板串匹配模板串的[1,i]位。我们选择初始化 i = 2，是因为 ne[1]=0 始终成立。

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // s[] 为模式串，p[] 为模板串

    // 首先求 next[]
    for(int i = 2, j = 0; i <= p.size(); 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 <= s.size(); i ++){
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == p.size()){
          j = ne[j]; // 继续寻找下一个
          //  匹配成功后的逻辑
        }
    }

Trie 树

  • 用途：高效存取和查找字符串集合

  • 思路：每个节点存储一位字符

  • 模板

    • 0 号点既是根节点，又是空节点
    • son[][] 存储树中每个节点的子节点，实际上所有的点是对应 idx
    • cnt[] 存储以每个节点结尾的单词数量
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    int son[N][26], cnt[N], idx = 0;

    // 插入字符串
    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] ++;
    }

    // 查询字符串出现次数
    void query(char *str){
        int p = 0;
        for (int i = 0; str[i]; i ++){
          int u = str[i] - 'u';
          if (!son[p][u]) return 0;
          p = son[p][u];
        }
        return cnt[p];
    }

并查集

  • 面试中常见，因为结构简单、构思巧妙

  • 解决问题：

    1. 合并：将两个不相交的集合合并位一个集合
    2. 查询：查询两个元素是否在同一个集合中

  • 思想：树结构，每个点指向其父节点

    • 路径压缩：把沿途的每个节点的父节点都设为祖先节点
    • 按秩合并：不常见

  • 模板

    • 朴素并查集
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int p[N]; // 存储各个节点的祖先节点

    // 返回 x 的祖先节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，节点编号 1~n，各个节点的祖先节点为自己；
    for (int i = 1; i <= n; i ++) p[i] = i;

    // 合并 a 和 b 所在的集合，相当于让 a 的祖先节点为 b
    p[find(a)] = find(b);
    • 维护 size 的并查集
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // p[] 存储各个节点的祖先节点
    // cnt[] 只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
    int p[N], cnt[N];

    // 返回 x 的祖先节点
    int find(int x){
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，节点编号 1~n，各个节点的祖先节点为自己；
    for (int i = 1; i <= n; i ++){
        p[i] = i;
        cnt[i] = 1;
    }

    // 合并 a 和 b 所在的集合，相当于让 a 的祖先节点为 b
    cnt[find(b)] += cnt[find(a)];
    p[find(a)] = find(b);
    • 维护到祖宗节点距离的并查集
    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
    // p[] 存储各个节点的祖先节点
    // d[x] 存储 x 到祖先节点的距离
    int p[N], d[N];


    // 返回 x 的祖先节点
    int find(int x){
        if (p[x] != x){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，节点编号 1~n，各个节点的祖先节点为自己；
    for (int i = 1; i <= n; i ++){
        p[i] = i;
        d[i] = 0;
    }

    // 合并 a 和 b 所在的集合，相当于让 a 的祖先节点为 b
    p[find(a)] = find(b);  
    cnt[find(a)] = distance; // 根据具体问题，初始化 find(a) 的偏移量

堆

  • 堆：每个节点的值总是不大于或不小于其父节点的值

  • 堆一定是完全二叉树，所以存储方式和之前的数组模拟链表不同，采用下标标记点的位置

    • 下标为 x 的点的两个左右子节点为 2 * x 和 2 * x + 1
      • 所以从 1 开始

  • 进行 down 操作时必须满足左儿子和右儿子已经是个堆

  • 堆排序：不断的取 h[1]，注意堆本身不一定有序，只能保证父子节点之间的单调性

  • 模板

    • h[N]存储堆中的值, h[1] 是堆顶，ph[k] 存储第 k 个插入的点在堆中的位置，hp[k] 存储堆中下标是k的点是第几个插入的
    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
    int h[N], hp[N], ph[N], size;

    // 交换堆中两点及其映射
    void heap_swap(int a, int b){
        swap(ph[hp[a]], ph[hp[b]]);
        swap(hp[a], hp[b]);
        swap(h[a], h[b]);
    }

    // down 和 up 为基础操作

    // 递归写法
    void down(int u){
        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t){
          heap_swap(u, t);
          down(t);
        }
    }

    // 循环写法
    void up(int u){
        while (u / 2 && h[u]  < h[u / 2]){
            heap_swap(u, u / 2);
            u >>= 1;
        }
    }

    // O(n) 建堆，从 n / 2 开始是因为最后的叶节点已经是最下一层
    for (int i = n / 2; i; i --) down(i);

    • 插入一个数

      1
      2
      h[++ size] = x;
      up(x);

    • 求集合中最小值

      1
      h[1];

    • 删除最小值

      1
      2
      3
      heap[1] = heap[size];
      size --;
      down(1);

    • 删除任意一个元素

      1
      2
      3
      4
      heap[k] = heap[size]; 
      size --;
      down(k);
      up(k)

    • 修改任意一个元素

      1
      2
      3
      heap[k] = x;
      down(k);
      up(k)

Hash 表

一般哈希

  • 常用：插入、查询（删除一般是直接标记）
  • 由于把区间变小了，所以一般要模 N。因为减少冲突，一般取 N 为素数

拉链法

  • h[] 中存储对应链表的head头指针

  • 模板

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

    // 向哈希表中插入一个数
    void insert(int x){
      int k = (k %  N + N) % N; // 这么写是因为在 C++ 中负数的模仍然是负数
      e[idx] = x;
      ne[idx] = h[k];
      h[k] = idx ++;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x){
      int k = (k % N + N) % N;
      for (int i = h[k]; i != -1; i = ne[i]);
    }

开放寻址法

  • 开放寻址法的好处是不需要开辟额外的数组，但是为了减少空间，一般会把 Hash 表的空间开大（约 拉链法 的 2 倍）

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int h{N};

    // 如果 x 在哈希表中，返回 x 的下标；否则返回 x 应该插入的位置

    int find(int x){
      int t = (x % N + N) %N;
      while(h[t] != null && h[t] != x){
        t ++;
        if(t == N) t = 0;
      }
      return t;
    }

字符串哈希

  • 核心思路：将字符串看成 P 进制数

    • P 的经验值是 131 或 13331，取这两个值的冲突概率低
    • 一般我们假设 RP 足够好，不会发生碰撞

  • KMP 的有力竞争对手
    -小技巧：取模的数用 2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    typedef unsigned long long ULL;
    ULL h[N], p[N]; // h[k] 存储字符串前 k 个字母的哈希值，p[k] 存储 p^k mod 2^64 便于计算

    // 初始化
    p[0] = 1;
    for (int i = 1; i <= n; i ++){
      h[i] = h[i - 1] * P + str[i];
      p[i] = p[i - 1] * P;
    }

    // 计算字串 str[l ~ r] 的哈希值，这个思想类似于前缀和
    ULL get(int l, int r){
      return h[r] - h[l - 1] * p[r - l + 1];
    }

算法备忘录系列目录：
第一节 算法备忘录·基础算法
第二节 算法备忘录·数据结构
第三节 算法备忘录·STL
第四节 算法备忘录·搜索与图论
第五节 算法备忘录·数学知识
第六节 算法备忘录·动态规划
第七节 算法备忘录·贪心
第八节 算法备忘录·时空复杂度分析

笔记
#计算机 #算法
算法备忘录·数据结构
https://justloseit.top/算法备忘录·数据结构/
作者
Mobilis In Mobili
发布于
2021年8月7日
更新于
2022年11月21日
许可协议