9.12

[Ryanlyt]

链表与邻接表：树与图的存储

实现方式多种 链表可以用指针加结构体实现(写工程时一般用动态链表) 用数组模拟(称为静态链表)

为什么用数组模拟 效率 new Node();非常慢（new出来很慢），而数组模拟快 笔试时一般不采用动态链表的方式

(用数组模拟)单链表

• 用的最多的是邻接表（存储图和树）

e[N], ne[N] 用下标关联起来

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a（用的最多，算法题里80％的情况都是把一个新的点插入头结点的位置）
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在（算法题里不用考虑内存泄漏的问题）
void remove()
{
    head = ne[head];
}
//
//将x插到下标是k的点后面
void add(int k, int x){
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

//将下标是k的点后边的节点删除
void remove(int k){
    ne[k] = ne[ne[k]];
}

(用数组模拟)双链表

• 用来优化某些问题

  
  // e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
  int e[N], l[N], r[N], idx;

// 初始化 void init() { //0是左端点，1是右端点 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 ++ ; }

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

![_59ce2553a4f373ca7f83e2c329d24b08_1942241772_Screenshot_2023-09-12-10-59-57-606_com alicloud databox](https://github.com/Ryanlyt/algorithm-learning/assets/72852969/0aab3700-d0d4-49bd-b67f-e03dfea31beb)

![_238a72eae7dd77f0119136c79691de05_-1898836845_Screenshot_2023-09-12-11-00-03-780_com alicloud databox](https://github.com/Ryanlyt/algorithm-learning/assets/72852969/3e3b90dd-f0ea-4f0d-a0f4-8b1855de4a5c)

![_5bc1ab0b53297de83f523f22312f891b_2028129746_Screenshot_2023-09-12-11-44-45-255_com alicloud databox](https://github.com/Ryanlyt/algorithm-learning/assets/72852969/46f17a0b-2e13-4d8f-8114-cd1b92bec431)

![_55ecec3e52a69af9e85a5910f40d408c_1199594925_Screenshot_2023-09-12-11-45-22-746_com alicloud databox](https://github.com/Ryanlyt/algorithm-learning/assets/72852969/4ea8654c-ee17-44e2-abce-eab3bffe0db7)

![_31da7c5f2d2a0994591957e8144797ac_1959423333_Screenshot_2023-09-12-11-45-27-606_com alicloud databox](https://github.com/Ryanlyt/algorithm-learning/assets/72852969/ad28869a-2488-4caf-93e6-0bdbb38b47bb)

[Ryanlyt]

栈与队列

栈和队列可以用stl里的容器直接写 stl能做的数组一定也能做；数组可以做的，stl不一定能做 用数组模拟栈

// tt表示栈顶
int stk[N], tt = 0;

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

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

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}

用数组模拟队列

普通队列（循环队列就是插入和弹出的时候都加个判断）

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

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

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

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

单调栈单调队列对应的题型很少 思路：先把用栈和队列做的朴素做法想清楚，然后想想哪些元素是没有用的，删去这些元素看看剩下的元素有无单调性，若有，则可优化（极值用栈顶栈底队列头队列尾、找某一个值用二分） 单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; 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;
}

[Ryanlyt]

kmp

算法题的思路： 1、暴力算法怎么做 2、如何优化

//字符串模式匹配暴力算法
char S[N], p[M]
for(int i = 1; i <= n; i++){
    bool flag = true;
    for(int j = 1; j <= m; j++){
        if(S[i] != p[j]){
            flag = false;
            break;
        }
    }
}

kmp算法习惯上下标从1开始

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：(next[1] = 0，不用算)
for (int i = 2, j = 0; i <= m; 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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

[Ryanlyt]

Trie树

用于快速高效存储和查找字符串集合的数据结构 （凡是用到Trie树的题目字符串要么全是大写、要么全是小写、数字、0和1，总之字符的种类不多）

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

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

[Ryanlyt]

并查集

容易出的的数据结构 因为代码短，思路精巧

并查集适用场景： 1、将两个集合合并 2、询问两个元素是否在一个集合中

基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点储存它的父节点，p[x]表示x的父节点

问题1：如何判断树根: if (p[x] == x) 问题2：如何求x的集合编号: while(p[x] != x) x = p[x]; 问题3：如何合并两个集合: px是x的集合编号，py是y的集合编号。p[x] = y

优化: 路径压缩

朴素并查集
    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所在的两个集合：
    p[find(a)] = find(b);

维护size的并查集
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回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;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

维护到祖宗节点距离的并查集
    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回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所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

[Ryanlyt]

堆

堆是一棵完全二叉树

如何手写一个堆 1、插入一个数 heap[++size] = x; up(size); 2、求集合中的最小值 heap[1] 3、删除最小值 heap[1] = heap[size]; size--; down(1); 此3个操作stl里的堆支持（stl里的堆就是优先队列）
4、删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k); 5、修改任意一个元素 heap[k] = x; down(k); up(k);

堆的存储：用一个数组（下标从1开始更方便） x的左儿子：2x
x的右儿子：2x+1

堆的两个基本操作 down(x) 往下调整 up(x) 往上调整 上述5个操作可以由这两个操作组合而成

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系（注意：一般用的堆不需要那么麻烦的swap，但在迪杰斯特拉算法中需要用到）
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

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)建堆
for (int i = n / 2; i; i -- ) down(i);

[Ryanlyt]

哈希表

离散化是一种很特殊的哈希，因为离散化还要求有单调性

哈希表的主要用途：把比较大的值域映射到比较小的空间(从0 - N，N比较小)（操作数比较少）

哈希表一般用于执行的操作只有：插入和查找（很少删除）

哈希表里面一般不需要用sort

一般哈希

哈希函数模的数一般取质数 根据冲突处理的不同可以分为拉链法和开放寻址法

(1) 拉链法（开一个数组+链表）

    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N; //为什么+N % N？ 因为x % N在c++里可能是负数，这样可以保证k为正数 
        e[idx] = x;
        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])    //遍历单链表
            if (e[i] == x)
                return true;

        return false;
    }

////注意：用之前要memset(h, -1, sizeof h);

(2) 开放寻址法（只需要开一个数组，但一般要多开2-3倍）

    int h[N];

    // 如果x在哈希表中，返回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;
    }

////注意：使用之前要memset(h, 0x3f, sizeof h); （先定义一个范围外（很大的值）作为null，如 const null = 0x3f3f3f3f，表示这个位置没人）
//memset是按字节来memset的，h是int型数组（memset(h , 0, sizeof h), (memset(h, -1, sizeof h))）

字符串哈希

有很多字符串的问题都可以用哈希来做，不一定非要kmp（kmp可以用来求循环节，但字符串哈希不能；除此之外，字符串哈希优于kmp） 需要快速判断两个字符串是否相等可以用此做法

字符串前缀哈希法（很🐂，需要掌握）
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低（和前面的哈希有所出入，不考虑冲突）（不能映射成0）
（字符串位置从1开始编号）（实现从1开始编号可以：scanf("%d%d%s", &n, &m, str + 1)）
小技巧：取模的数用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];    //用到了ASCII码
    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];
}

[Ryanlyt]

C++ STL容器

vector, 变长数组，倍增的思想（系统为某一程序分配空间时，所需时间与空间大小无关，与申请次数有关）
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()    （vector的迭代器<可以看成是指针>：begin是第0个数，end是最后一个数的后面一个数）
    []
    支持比较运算，按字典序

//遍历方法
for(int i = 0; i < vec.size(); i++) cout << vec[i] << ' ';
cout << endl;
for(vector<int>::iterator i = vec.begin(); i != vec.end(); i++) cout << *i << ' ';
//vec.begin()其实就是vec[0]，vec.end()其实就是vec[vec.size()]
cout << endl;
for(auto &v : vec) cout << v << ' ' ;
cout << endl;

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    p = make_pair(12, 23);   p = {20, 21};    存三个可以: pair<int, pair<int, int>> p;
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串（当第二个参数过大或者没写，返回到最后一个字符）
    c_str()  返回字符串所在字符数组的起始地址    printf("%s\n", str.c_str());
    str += "def";
    str1.append(str2);

queue, 队列
 （没有clear()，要清空，直接重新构造一个队列，q = queue<int>();）
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆（比queue用得更多)
    size()
    empty()
    (没有clear()）
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列（加强版的vector，速度稍微慢一些）
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)（map最主要使用的，🐂，可以向数组一样使用map，如：map<string, int> a;  a["lyt"] = 1;  cout << a["lyt"] << endl;）
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

string.find()