第二讲数据结构¶

如何用数组来模拟这些数据结构，而不用结构体，主要是效率问题

struct Node {
    int val;
    Node *nest;
};
// 在面试题里多，但是在笔试题里面比较少
new Node(); // 非常慢，new几百万个节点就能直接超时了

链表与邻接表¶

什么是链表，每个点存两个值，一个是自己的值，一个指向下一个节点

两种链表：单链表、双链表

单链表中用的最多的是邻接表，邻接表其实是n个链表，最主要的应用：存储图和树

双链表的作用是优化某些问题

每个点都会存一个值和一个next指针

用数组来模拟需要先定义 e[N], ne[N]

用下标关联起来

空节点用-1表示

0号点的指针是e[0] = val, ne[0] = 1

链子一样，可以沿着链子遍历整个数组

单链表¶

单链表模板：

// head存储链表头（头节点的下标），e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点（存储当前已经用到了什么地址）
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1; // 指向队尾
    idx = 0; // 每个点都没有被分配
}

// 在链表头插入一个数a 
void insert(int a)
{
    e[idx] = a;
    ne[idx] = head;
    head = idx;
    idx++;
}
// 将一个点插到下标是k的点的后面
void insert(int k, int a) {
    e[idx] = a;
    ne[idx] = ne[k]; // 指向k节点的下一个位置
    ne[k] = idx;
    idx++;
}
// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

// 将下标是k的点的后面的点删掉
// 只需要将指针指向下下个点即可，其他不用变
void remove(int k) {
    ne[k] = ne[ne[k]];
}

数组的好处就是快，比动态链表快很多，C++用new巨慢，算法题的时候会超时

数组模拟链表被叫做静态链表

单链表只能知道下一个节点的东西，不能知道前一个节点，要知道的话只能从head开始遍历

算法题不用考虑内存泄漏的问题，删除实际上会浪费一个数组空间，但是不用考虑

826. 单链表¶

删除第k个插入的数后面的数，就是删除下标是k-1的点

在第k个插入的数后插入一个数就是，在下标是k-1的点后面插入一个数

比如I 1 1 其实就是在小表示0的点后面插入一个数值1

删除头节点，就是把整条链表删除了

#include <iostream>

using namespace std;

const int N = 100010;

// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx存储当前已经用到了哪个地址，相当于指针
int head, e[N], ne[N], idx;

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

// 将x插到头节点
void add_to_head (int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 将一个点插到下标是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]];
}

int main () {
    int m;
    cin >> m;

    init();

    while(m--) {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_to_head(x);
        } else if (op == 'D') {
            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);
        } else {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) {
        cout << e[i] << ' ';
    }

    cout << endl;
    return 0;
}

双链表¶

双链表就是每个节点有两个指针，一个指向前面，一个指向后面

在这里就不需要head了，让0号点成为head，而1号点就是我们的tail

双链表模板：

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

如果想要使用结构体，也很简单：

struct Node {
    int e, l, r;
} nodes[N];

邻接表就是一堆单链表

827.双链表¶

双链表head是0， tail是1

双链表往往不需要左端点和右端点的值

循环双链表¶

就是头和尾互相指一下，这样链表就变成一个圈了

栈¶

栈是先进后出，像一个单口的罐子，所以先放进去的后拿出来

队列是先进先出，像双口的罐子，从下面接着

栈模板题：

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

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

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

// 栈顶的值
stk[tt];

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

}

// 栈顶元素就是
stk[tt];

考验的是记忆力和毅力（自制力）

队列¶

普通队列：

// hh 表示队头，tt表示队尾
// 栈是从0开始，队列是从-1开始
// hh和tt之间的东西就是我们的队列
int q[N], hh = 0, tt = -1;

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

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

// 队头的值
q[hh];

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

}

循环队列：

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

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

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

// 队头的值
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;
}

思路是：假设a3 >= a4，那么当循环到a5以后的值的话，a3包括a3之前的数都是没有用的，直接删除即可

830.单调栈¶

思考2，4，5，3，3

tt = 1的时候，stk[tt]存储的才是数列的第一个值！

stk[0] 存储的是0

对于3，tt就得不断往前找，找到2这个数，即tt = 1的时候，这时候输出stk[1] ，然后使的stk[2]变成3。因为对于4和5来说，有比他们小的3在，比不可能输出他们两个。但是2还是有可能的。

对于第二个3，因为stk[2] 也等于3，所以输出的是stk[tt =1] = 2

这样做的好处是：栈里面存储的数是单调递增的，而且对于每个数只会进栈一次+出栈一次，算法时间复杂度就是O(n)

另外cin和cout比printf和scanf慢了10倍

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt;

int main () {
    cin >> n;
    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;
    }
    return 0;
}

单调队列¶

最经典的题就是滑动窗口中的最大值或者最小值

多重背包也可以用单调队列优化

单调栈和单调队列都是先想暴力做法，然后找单调性，进行优化

单调队列模板：

常见模型：找出滑动窗口中的最大值/最小值
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;
}

用队列来维护窗口，每次向前移动的话，tt都会++来输入一个数到队尾，hh都会++吐出一个数

只要某个数的前面有比他大的数，那么那个数不仅会比他先被弹出，而且不可能会被输出

通过判断使队列中的数严格单调上升

一个严格单调上升的队列只要输出q[hh] 即可

这里的的q[]里面存的是下标

154. 滑动窗口¶

#include <iostream>

using namespace std;

const int N = 1000010;

int n, k;
int a[N], q[N];

int main () {
    scanf("%d%d", &n, &k);
    // a中存的是数
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    //q中存的是下标
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        // 先判断队头是否已经滑出窗口
        // 每次队列里面最多只有一个数不在窗口内，所以使用if，而不是while
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt--;
        // i有可能是最小值
        // a[i]足够小，可能把整个数组清空了
        // 所以要先添加i
        q[++tt] = i;        
        if (i >= k - 1) printf("%d ", a[q[hh]]);

    }

    puts("");


    hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        // 先判断队头是否已经滑出窗口
        // 每次队列里面最多只有一个数不在窗口内，所以使用if，而不是while
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt--;
        // i有可能是最小值
        q[++tt] = i;        
        if (i >= k - 1) printf("%d ", a[q[hh]]);

    }

    puts("");
    return 0;
}

KMP¶

注意国内算法圈的KMP不是真正的KMP，更多的是用KMP去寻找border

KMP暴力做法：

for (int i = 1; i <= n; i ++ )
{
    bool flag = true;
    for (int j = 1; j <= m; j ++ )
    {
        if (s[i + j - 1] != p[j])
        {
            flag=false;
            break;
        }
    }
}

KMP模板：

KMP习惯上从1开始

next数组是对于模式串而言的。P 的 next 数组定义为：next[i] 表示 P[0] ~ P[i] 这一个子串，使得 前k个字符恰等于后k个字符 的最大的k. 特别地，k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）。

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
    // j是计数，记的是当前缀字母串和后缀字母串相同时，最大的字母串长度
    // ne[i]存储的是前i个字符串中最大的（前缀和后缀相同的）长度

    // 对于新的ne[i]来说，在没有更新j之前，j还代表了ne[i - 1], 下面while判断中的j就是ne[i - 1]的意思
    // (如果前j位数相同，注意p中存储的数下标是从1开始的，所以即p[j]和老p[i]相同)，如果需要判断的新p[i]和p[j + 1]，如果相同的话就j++
    // 如果不相同的话，就要去找出p[0]到p[j] 中的最大前缀和后缀相同的长度，来试试是否可以加在小字符串的后面

    // 如果想不清楚while判断过程，可以用abcabdabcabc来进行举例


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];
        // 匹配成功后的逻辑
    }
}

注意在C++中数组命名成next有可能会报错，所以使用ne[N] 比较保险一些

关于字符数组输入的小trick¶

char p[N];
cin >> p + 1; // 合法，因为在终端读入的就是字符

int p[N];
cin >> p + 1; // 不合法，因为在终端读入的就是字符，std::basic_istream<char>和int *的类型不匹配

实例：

#include <iostream>
#include <cstdio>

using namespace std;
//int n;
char p[3];
char s[4];

int main () {
    cin >> p + 1 >> s + 2;
    for (int i = 0; i < 3; i++) cout << i << ' ' << p[i] << endl;
    cout << "---------" << endl;
    for (int i= 0; i < 4; i++) cout << i << ' ' << s[i] << endl;
    return 0;
}

// 输入：
12
12

// 输出：
0
1 1
2 2
---------
0
1
2 1
3 2

next数组是对于模式串而言的

831. KMP¶

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

char p[N], s[M];

// n是patter的长度，m是s的长度
int n, m; 

int ne[N];

int main () {
    cin >> n >> p + 1 >> m >> s + 1; // 注意都是从1开始进行存储

    // 先处理pattern的ne[]数组
    for (int i = 2, j = 0; i <= n; i++) { // 注意这里不是从i = 0开始！
        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 <= m; i++) { // 注意这里不是从i = 0开始！
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n) {
            printf("%d ", i - n); // 这道题输出的下标是从0开始的，就不用+1了
            j = ne[j];
        }
    }
    return 0;
}

Trie树/字典树¶

非常简单的数据结构

用来高效地快速存储和查找字符串集合的数据结构

支持两个操作

长得是一个字典地形式，字母地类型一般不是很多

如何高效地存储这些字符串

存储¶

有个根节点，root

从前往后遍历每个字符，每到一个字符如果没有这个节点就创建它

给每串字符地末尾节点打个标记，用来检索这个单词

查找¶

沿着各个节点依次查找，如果不存在路径那么就是不存在的，如果没有标记那么也是不存在这个字符串的

son[N][26]一维是结点总数，而结点和结点之间的关系（谁是谁儿子）存在第二个维度，比如[0][1]=2, [0]表示根节点，[1]表示它有一个儿子‘b’,这个儿子的下标是2；接着如果有一个[2][2]=8 ; 说明根节点的儿子‘b’也有一个儿子‘c’，这个孙子的下标就是8；这样传递下去，就是一个字符串。随便给一个结点][x][y], 并不能看出它在第几层，只能知道，它的儿子是谁。

关于理解int son[N][26] 这个二维数组的心得

Tire树本质上一个多叉树，最多可以分多少叉呢？因为此题存的都是小写字母，所以是26叉；

这里就解释了son这个二维数组的第二维的含义，就是他最多有26个孩子，那么他是谁呢，他当然是结点了，那结点之间怎么区分，或者这些孩子的爸爸叫啥，爸爸们用下标来区别，所以第一维就是爸爸们的id，son[0][1]含义就是0号爸爸有个儿子b ，那son[0][1] = 2，就是0号爸爸有个儿子b，儿子的id是2； 这些id就是由idx` 来赋值的；

idx可以理解为计划生育的管理局的给上户口的，生一个孩子，给孩子上身份证，证件上ID 为++idx ，而孩子叫啥，其实就是26个小写字母中的其中一个了；

对于每个结点而言，可以知道他有没有这个孩子，有的话叫啥，在哪里；

对于查询，从根节点一路查下来，就可以找到某个字符串在不在；

对于插入字符串，也是一路下来，看有没有这个儿子，没有了给你生个儿子，有了继续给下面找，所以只插入该字符串中原来不存在的字符即可； 也就是利用了公共前缀来降低查询时间的开销以达到提高效率的目的;

“Trie这个名字取自“retrieval”，检索，因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。”

Trie模板：

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

835. Trie字符串统计¶

#include <iostream>

using namespace std;

const int N = 100010;
char str[N];

// 对于每个节点最多只会向外连26条边
// cnt存储的是以当前这个点结尾的个数有多少个
// idx当前用到哪个下标
//下标是0， 既是根节点，又是空节点
int son[N][26], cnt[N], idx;

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


int main () {
    int n;
    scanf("%d", &n);
    while(n --) {
        char op[2];
        scanf("%s%s", op, str);
        if (op[0] == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

并查集¶

常用算法

代码很短，但是思路精巧，面试非常喜欢出

并查集作用：（近乎O(1)）

快速将两个集合合并
快速询问两个元素是否在一个集合当中

暴力操作非常耗时

基本思想和原理：用树的形式来维护所有的集合，每个集合用一棵树来表示

每个集合的编号就是根节点的编号，树根的编号就是整个集合的编号

对每个点都存储它的父节点是谁，p[x]来表示x的父节点

问题1：如何判断树根：if(p[x] == x) 除了根节点之外都不想等

问题2：如何求x的集合编号：while(p[x] != x) x = p[x]; 这一步时间复杂读还挺高的，需要优化

问题3：如何合并两个集合：将其中一个的根节点变成另外一个集合根节点的父亲即可。p[x]是x的集合编号，p[y]是y的集合编号，p[x] = y即可

并查集的优化（并查集路径压缩算法）：当找到祖宗节点的时候，将所有的路径点都直接指向祖宗节点，优化之后差不多是O(1)的时间复杂度

并查集经常需要维护额外信息

并查集模板：

(1)朴素并查集：

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


(2)维护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);


(3)维护到祖宗节点距离的并查集：

    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)的偏移量

836.合并集合¶

#include <iostream>
using namespace std;
const int N = 100010;
int p[N];
int n, m;

//并查集中最核心的操作
int find(int x) {
    // 返回x所在集合的编号（祖宗节点） + 加上路径压缩算法
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main () {
    // 因为每个数都是一个集合，所以先初始化
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) p[i] = i;

    while(m --) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M') p[find(a)] = find(b);
        else {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

在图中

能从a走到b又能从b走到a，那他们就在一个连通块里面的

837. 连通块中点的数量¶

#include <iostream>
using namespace std;
const int N = 100010;
//只保证根节点的size有意义
int p[N];
int Size[N];
int n, m;

//并查集中最核心的操作
int find(int x) {
    // 返回x所在集合的编号（祖宗节点） + 加上路径压缩算法
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main () {
    // 因为每个数都是一个集合，所以先初始化
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) {
        p[i] = i;
        Size[i] = 1;
    }

    while(m --) {
        char op[5];
        int a, b;
        scanf("%s", op);

        if (op[0] == 'C') {
            scanf("%d%d", &a, &b);

            // 特判一下ab是否在同一个集合中，如果是的话就不用加了
            if (find(a) == find(b)) continue;
            // 只需要维护根节点的size
            Size[find(b)] += Size[find(a)];
            p[find(a)] = find(b);
        }
        else if (op[1] == '1') {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        } else {
            scanf("%d", &a);
            printf("%d\n", Size[find(a)]);
        }
    }
    return 0;
}

堆（手写堆不是STL）¶

如何手写一个堆：(下标是从1开始的，如果是从0开始的话，0的左儿子就是0了，不太方便)

插入一个数 heap[++ size] = x;up(size); 堆的最后一个位置插入x然后不断上移
求整个集合当中的最小值 heap[1];
删除最小值 heap[1] = heap[size]; size--; down(1);用整个堆中的最后一个元素来覆盖掉堆顶的元素，然后下移（这么做的原因是一个一维数组删除头节点的数很困难，但是删除尾节点的数比较简单）
删除任意一个元素（STL不能直接实现）heap[k] = heap[size]; size--; down(k); up[k]（down和up只会执行一个）
修改任意一个元素（STL不能直接实现）heap[k] = x; down(k); up[k];

堆的性质¶

堆是一个二叉树，完全二叉树，除了最后一层节点，上面所有节点都是满的，不存在空的情况。最后一层是从左到右依次排列。

以小根堆为例，每一个点都是小于等于左右儿子的，根节点就是整个数据结构里的最小值

堆的存储¶

全新的存储方式：用一个一维的数据结构来存

1号点是根节点

节点x的左儿子是2x，x的右儿子是2x+1

一维数组就能存储一颗树

堆的操作¶

down(x)往下调整：就是如果堆里面如果某个值变大了，就要把他往下移，往下移的思路是和他的两个儿子比较，和其中一个较小的儿子进行交换，这样能保证小根堆的结构，交换到不能交换的时候就结束

整个过程就是把大的值往下压的过程（down）

up(x)网往上调整：将下面的数变大，只要把他跟他的父节点比较即可

堆的模板：

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[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]);
}

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

838. 堆排序¶

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int n, m;
int h[N], Size;

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) {
        swap(h[u], h[t]);
        down(t);
    }
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    Size = n;
    // 这一步的时候，相当于最后一层不用down
    // 按照完全二叉树的结构，最后一层的数的个数是n/2
    // 因为在down倒数第二层的时候，最后一层会自动被down，所以i从n/2开始即可
    for (int i = n/2; i; i -- ) down(i); // 这个循环的时间复杂度是O(n)
    while(m --) {
        printf("%d ", h[1]);
        // 这里不能直接按1，2，3这样的顺序输出的原因是：
        // 虽然能保证h[1]就是整个堆最小的数
        // 但是h[2]和h[3]顺序并没有定，他们两个中必定有一个第二小，但这个数可能是h[3]
        h[1] = h[Size];
        Size--;
        down(1);
    }
    return 0;
}

839.模拟堆¶

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

// ph[k]存的是第k个插入的数的下标是什么
// ph[k] = j, hp[j] = k;
// hp[j]就是知道下标是j的点，返回去找他是第几个插入的数

// hp表示第k个插入数现在的位置，hp表示在该位置的数是第k个插入的
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 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && 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;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}

哈希表¶

两大块内容，一个是普通哈希表的写法，另一个是字符串的哈希方法

哈希表：1. 存储结构：开放寻址法、拉链法（两种方法都很常用）2. 字符串常见的哈希方式

哈希表的主要作用：把庞大的空间和值域映射到比较小的空间，映射到0-N，N一般比较小

把从0-10^9 映射到0-10^5的值域

一般哈希¶

一般哈希模板：

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        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;
    }

(2) 开放寻址法
    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;
    }

840. 模拟散列表¶

通过一个哈希函数

哈希就是离散

离散化就是及其特殊的哈希方式

离散化是需要保序的，单调递增

从0~10^{9映射到0~10}5

操作的个数是10^{5每一个数的范围是-10}9 ~10^9

输入h(x) 映射到输出（0，10^5）

x mod 10^5（哈希函数怎么写：只要将大数取模就行了）（模的这个数最好取成质数，并且离2的整次幂尽可能远）
冲突两个不一样的数会被映射成同一个数，两种处理方法：开放寻址法和拉链法

拉链法：开一个一维数组来存所有的哈希值

当原数被映射到新的数据范围的时候，新的数据范围就会拉一条槽下来，依次连接被赋成新数的多个原数

在链上增加的时候，可以是头插也可以尾插

哈希表是一个期望算法

平均下来每条链是常数，可以被看成O（1）

在算法题里面，一般只有添加和查找操作，不会删除

添加：h(x)

查找：h(x)在哪个槽上，遍历一遍有没有这个数

寻找大于100000的第一个质数：答案是100003

#include <iostream>
using namespace std;

const int N = 100010;


int main () {
    for (int i = 100000;;i++) {
        bool flag = true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

840. 模拟散列表¶

拉链法¶

#include <iostream>
#include <cstring>
using namespace std; 

const int N = 100003;
int h[N], e[N], ne[N], idx;

void insert (int x) {
    // 在数学里面-10 mod 3应该是2，因为-10=-4 * 3 + 2
    // 而在C里面-10 mod3得到的是-1
    // 而且不能（x + N）%N原因是x+N仍然可能是负数，加了没用
    // 必须先模再加再模
    int k = (x % N + N) % N; // +N的目的是让余数变成正数,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;
}

int main () {
    int n;
    scanf("%d", &n);

    memset(h, -1, sizeof h); // 先把链表清空，空指针一般用-1表示

    while (n --) {
        char op[2];//尽量读字符串
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') insert(x);
        else {
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

开放寻址法¶

只开一个一维数组，但是这个数组的长度经验上来说要开到题目数值范围的两到三倍

100000的数需要开到二三十万

添加：h(k) 的位置有人就去下一个坑位，直到找到没有人的坑位

查找：也是从第k个坑位开始，从前往后找

删除：如果找到x的话，在数组里面打个标记来指出他被删除了

开放寻址法的好处是只用开一个数组

大于二十万最小的质数是200003

开放寻址法的核心是find函数，如果存在返回x位置，如果不存在，返回应该存储的位置

注意memset()是按字节赋值，写0x3f3f3f3f就会报错

在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。

比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。

而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。

所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：

0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^{9数量级，而一般场合下的数据都是小于10}9的。 0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。

经验上来说，每个数只要找两三个坑位就能找到了

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];

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

int main()
{
    memset(h, 0x3f, sizeof h);

    int n;
    scanf("%d", &n);

    while (n -- )
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }

    return 0;
}

字符串哈希¶

基本想法：将字符串映射成整数

假设所有字符串都是小写字母，将一个字符串看成p进制的数然后模上一个Q的结果

比如abcabcdefg

1231234567 = (1* p^9 + 2* p^8 + 3 * p ^7...) %q = 0~q - 1这个值就是哈希值

p一般取131或者13331，q取2^64，因为可以直接用unsigned long long 8bit 最多只能存储2^64，超出的部分会自动取模

取模运算比加减乘除慢了很多倍，所以要用unsigned long long

hash(abd) = (124)131 = 131 * 131 + 2 * 131 + 4 * 1

一种特殊的哈希方式，字符串前缀哈希法

h[n] 表示前n个字符的哈希

str = "ABCA"

h[0] = 0;

h[1] = "A"的hash值

h[2] = "AB"的hash值

将字符串看成p进制的数，比如ABCD字符串可以看成（1，2，3，4），1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p ^0,然后给这个值modQ
注意不能将某个字母映射成0，因为0的p进制数永远是0，“AAA”和“AA”都是0
哈希数字的时候可以容忍冲突，哈希字符串做法要假定人品足够好，碰不到冲突的情况，所以这个方法完全不考虑重冲突情况
一般来说，p取131或者13331，Q取2^64,我们就能假定碰不到冲突的情况了
可以利用哈希计算出所有子串的哈希

比如：需要求出一个字符串从L到R的字符串的哈希值，公式就是h[R] - h[L] * p^(R - L +1)

字符串哈希：

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用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;+9
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

哈希值相同的话就认为两个字符串相同

h[N]表示的是某一个前缀的哈希值

p代表p进制

841. 字符串哈希¶

考虑一下abab就懂了

h[1] = 1

h[2] = 1 * 131 + 2

h[3] = 1*131 ^ 2 + 2 * 131 + 1

h[4] = 1 * 131 ^3 + 2 * 131 ^2 +1 * 131 + 1

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main () {
    scanf("%d%d%s", &n, &m, str + 1); // 加一是为了防止从0开始
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i]; // 所以最左边的那一位最后会变成 P^(n - 1)
    }

    while (m --){
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

C++ STL简介¶

vector

数组长度是动态变化的

string

处理字符串的利器

queue, priority_queue

stack

deque

set, map, multiset, multimap

unoredered_set, unordered_map, unordered_multiset, unordered_multimap

bitset

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int> 好处是相当于一个自带的结构体，而且自带了一个比较
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    p = make_pair(10, "yxc"); // 可以生成pair
    p = {20, "abv"}; // C++11可以直接写
    pair<int, pair<int, int>> p // 可以做到存储三个不同的变量

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串，注意第二个参数是长度！
    c_str()  返回字符串所在字符数组的起始地址、头指针
    printf("%s\n", a.c_str());

queue, 队列，先进先出，没有clear
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素
    q = queue<int>(); 能够直接清空q，而不需要用到clear

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆可以向里面插入-x
    定义成小根堆的方式：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, 基于平衡二叉树（红黑树），动态维护有序序列
    set里面是不能有重复元素的，而multiset里面可以有
    set所有操作的时间复杂读是log(n)
    size()
    empty() 
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)前驱就是前面一个数，后继就是后面一个数

    set/multiset
        insert()  插入一个数
        find()  查找一个数，不存在的话返回end迭代器
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)k是x个数 
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器 
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()
例子： map<string,int> a; a["yxc"] = 1; cout << a["yxc"] << endl;

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 基于哈希表实现的
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--,因为内部是没有序的

bitset, 圧位
    比正常的bool数组省内存，八分之一
    10000*10000的bool矩阵需要10^8 100MB，而bitset只需要12MB

    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count()  返回有多少个1

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

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

list用的不多

#include ¶

vector是变长数组，支持随机访问，不支持在任意位置 O(1) 插入。为了保证效率，元素的增删一般应该在末尾进行。

系统为某一程序分配空间时，所需的时间，基本上与空间大小无关，与申请次数有关，系统分配长度为1和100的数组的时间是一样的

变长数组要经量减少申请空间的次数

1.1声明¶

#include <vector>   // 头文件
vector<int> a;      // 相当于一个长度动态变化的int数组
vector<int> b[233]; // 相当于第一维长233，第二位长度动态变化的int数组
struct rec{…};
vector<rec> c;      // 自定义的结构体类型也可以保存在vector中

1.2 size/empty¶

size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是 O(1)所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。

1.3 clear¶

clear函数把vector清空。

1.4 迭代器¶

迭代器就像STL容器的“指针”，可以用星号*操作符解除引用。

一个保存int的vector的迭代器声明方法为：

vector<int>::iterator it; vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

1.5 begin/end¶

begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。

所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n 个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n = a.size()。

下面两份代码都遍历了vector a，并输出它的所有元素。

1.6 front/back¶

front函数返回vector的第一个元素，等价于a.begin()和a[0]。 back函数返回vector的最后一个元素，等价于--a.end()和a[a.size() – 1]。

1.7 push_back()和pop_back()¶

a.push_back(x)把元素x插入到vector a的尾部。 b.pop_back()删除vector a的最后一个元素。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main () {
    vector<int> a(10);
    vector<int> b(10, 3); // 长度为10的数组，并且全部初始化为3
    for (auto i : b) cout << i << ' ';
    cout << endl;

    vector<int> c;
    for (int i = 0; i < 10; i ++) c.push_back(i);

    for (int i = 0; i < 10; i++) cout << c[i] << ' ';
    cout << endl;

    for (vector<int>::iterator i = c.begin(); i != c.end(); i++) cout << *i << ' ';
    cout << endl;


    return 0;
}

第二讲 数据结构¶

链表与邻接表¶

单链表¶

826. 单链表¶

双链表¶

827.双链表¶

循环双链表¶

栈¶

队列¶

单调栈¶

830.单调栈¶

单调队列¶

154. 滑动窗口¶

KMP¶

关于字符数组输入的小trick¶

831. KMP¶

Trie树/字典树¶

存储¶

查找¶

835. Trie字符串统计¶

并查集¶

836.合并集合¶

837. 连通块中点的数量¶

堆（手写堆不是STL）¶

堆的性质¶

堆的存储¶

堆的操作¶

838. 堆排序¶

839.模拟堆¶

哈希表¶

一般哈希¶

840. 模拟散列表¶

840. 模拟散列表¶

拉链法¶

开放寻址法¶

字符串哈希¶

841. 字符串哈希¶

C++ STL简介¶

#include ¶

1.1声明¶

1.2 size/empty¶

1.3 clear¶

1.4 迭代器¶

1.5 begin/end¶

1.6 front/back¶

1.7 push_back()和pop_back()¶

第二讲数据结构¶