算法备忘录·数据结构

本文最后更新于:2021年9月12日 上午

一直以来,没能系统学习算法,是我心中的痛;现在学了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 总指向队尾元素的后一个位置——因为如果按照普通队列那样初始化,队尾就到了 N1N-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[]
    • 首先看 ppss 中是如何匹配的。设 ppss起始下标均为 1j 指向 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 * x2 * 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];
    }

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!