算法备忘录·数据结构

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

数据结构

链表

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

单链表

• 模板

  • head 储存链表头（直接记录了第一个节点的位置），e[] 存储节点的值，ne[] 存储节点指向的下一个节点位置，idx 表示当前用到哪个节点

  // 初始化
  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 开始。

  // 初始化
  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 总指向栈顶元素

  // tt 表示栈顶
  int stk[tt], tt = 0;
  
  // 向栈顶插入一个数
  stk[++ tt] = x;
  
  // 栈顶弹出一个数
  tt --;
  
  // 栈顶的值
  stk[tt];
  
  // 判断栈是否为空
  if (tt > 0){
  
  }

队列

• FIFO

普通队列

• 模板

  • 设队头初始为 1，队尾初始为 -1，表示空，tt 总指向队尾元素

  int q[N], hh = 0, tt = -1;
  
  // 向队尾插入一个数
  q[++ tt] = x;
  
  // 从队头弹出一个数
  hh ++；
  
  // 队头的值
  q[tt];
  
  // 判断队列是否为空
  if (hh <= tt){
  
  } 

循环队列

• 模板

  • 设队头初始为 0，队尾初始为 0，表示空，tt 总指向队尾元素的后一个位置——因为如果按照普通队列那样初始化，队尾就到了 $N-1$ 处

  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){
  
  } 

单调栈

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

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

• 模板（插入）

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

单调队列

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

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

• 模版（插入）

  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

• 问题：模板串 $p$ 在 模式串 $s$ 中 的匹配

• KMP 算法的思路

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

• 如何求 next[] ？

  • 首先看 $p$ 在 $s$ 中是如何匹配的。设 $p$ 和 $s$ 的起始下标均为 1，j 指向 $p$ 已经在 $s$ 中匹配的部分（因此，初始 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 始终成立。

• 模板

  // 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[] 存储以每个节点结尾的单词数量

  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. 查询：查询两个元素是否在同一个集合中

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

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

• 模板

  • 朴素并查集

  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 的并查集

  // 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);  

  • 维护到祖宗节点距离的并查集

  // 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的点是第几个插入的

  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);

  • 插入一个数

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

  • 求集合中最小值

    h[1];

  • 删除最小值

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

  • 删除任意一个元素

    heap[k] = heap[size]; 
    size --;
    down(k);
    up(k)

  • 修改任意一个元素

    heap[k] = x;
    down(k);
    up(k)

Hash 表

一般哈希

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

拉链法

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

• 模板

  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 倍）

• 模板

  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存储，溢出的结果就是取模的结果

• 模板

  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];
  }

---

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