• 【AcWing 学习】数据结构 + STL

    AcWing 数据结构 + STL

    参考：常用代码模板2——数据结构 - AcWing

    链表与邻接表

    使用结构体模拟：比较慢

    struct Node
{
    int val;
    Node *next;
};

    • 1
    • 2
    • 3
    • 4
    • 5

    使用数组模拟：

    int head; // 头节点的下标
int e[N]; // 值
int ne[N]; // 指向的下一个值
int idx; // 存储当前已经使用到哪个点

    • 1
    • 2
    • 3
    • 4

    单链表（静态链表）

    题目：826. 单链表 - AcWing题库

    数组模拟单链表：

    #include 
using namespace std;
const int N = 100010;

// head - 头节点的下标
// e[i] - 节点 i 的值
// ne[i] - 节点 i 的下一个节点的下标
// 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++;
}

// 将 x 插到下标 k 的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = 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;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    双链表（静态链表）

    题目：AcWing 827. 双链表 - AcWing

    #include 
using namespace std;
const int N = 1e5 + 10;

int e[N], l[N], r[N], idx;

// 初始化双链表
void init()
{
    // 0 表示左端点，1 表示右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在 k 下标的节点右边插入 x
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

// 在 k 下标的节点左边插入 x
// add(l[k], x);

// 删除 k 下标的节点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

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

    init();

    while (m--)
    {
        int k, x;
        string op; cin >> op;

        if (op == "L")
        {
            cin >> x;
            add(0, x); // 0 左端点
        }
        else if (op == "R")
        {
            cin >> x;
            add(l[1], x); // 1 右端点
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1); // k - 1 + 2
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else if (op == "IR")
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i])
        cout << e[i] << ' ';

    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    栈与队列

    模拟栈

    注意 t = 0 或 t = -1 主要影响的是 empty() 判断栈空的方法

    t = 0

    // s - 数组模拟栈，t - 栈顶指针
int s[N], t = 0; // *

// 向栈顶插入一个数 x
void push(int x)
{
    s[++t] = x;
}

// 从栈顶弹出一个数
void pop()
{
    t--;
}

// 判断栈是否为空
bool empty() 
{
    return t <= 0; // *
}

// 查询栈顶元素
int query()
{
    return s[t];
}

    • 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

    t = -1：

    // s - 数组模拟栈，t - 栈顶指针
int s[N], t = -1; // *

// 向栈顶插入一个数 x
void push(int x)
{
    s[++t] = x;
}

// 从栈顶弹出一个数
void pop()
{
    t--;
}

// 判断栈是否为空
bool empty() 
{
    return t < 0; // *
}

// 查询栈顶元素
int query()
{
    return s[t];
}

    • 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

    题目：828. 模拟栈 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10;

// implement stack

int main()
{
    int m; cin >> m;
    while (m--)
    {
        int x;
        string op; cin >> op;
        if (op == "push")
        {
            cin >> x;
            push(x);
        }
        else if (op == "pop")
        {
            pop();
        }
        else if (op == "empty")
        {
            cout << (empty() ? "YES" : "NO") << endl;
        }
        else if (op == "query")
        {
            cout << query() << endl;
        }
    }
    return 0;
}

    • 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

    模拟队列


    hh = 0，tt = -1：推荐

    // hh - 队头位置, tt - 队尾位置
int q[N], hh = 0, tt = -1;

// 向队尾插入一个 x
void push (int x)
{
    q[++tt] = x; // *
}

// 从队头弹出一个数
void pop ()
{
    hh++;
}

// 判断队列是否为空
bool empty () 
{
    return hh > tt; // *
}

// 查询队头元素
int query ()
{
    return q[hh];
}

    • 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

    hh = 0，tt = 0：

    // hh - 队头位置, tt - 队尾位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个 x
void push (int x)
{
    q[tt++] = x; // *
}

// 从队头弹出一个数
void pop ()
{
    hh++;
}

// 判断队列是否为空
bool empty () 
{
    return hh >= tt; // *
}

// 查询队头元素
int query ()
{
    return q[hh];
}

    • 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

    题目：829. 模拟队列 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10;

// implement queue ...

int main()
{
    int m; cin >> m;
    while (m --) 
    {
        int x;
        string op; cin >> op;
        if (op == "push")
        {
            cin >> x;
            push(x);
        }
        else if (op == "pop")
        {
            pop();
        }
        else if (op == "empty")
        {
            cout << (empty() ? "YES" : "NO") << endl;
        }
        else if (op == "query")
        {
            cout << query() << endl;
        }
    }
    return 0;
}

    • 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

    表达式求值

    题目：3302. 表达式求值 - AcWing题库

    #include 
#include 
#include 
using namespace std;

stack<int> num; // 存储数字的栈
stack<char> op; // 存储操作符的栈

// 优先级表
unordered_map<char, int> h {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

// 求值
void eval()
{
    // 第一个操作数
    int a = num.top(); num.pop();
    // 第二个操作数
    int b = num.top(); num.pop();
    // 运算符
    char p = op.top(); op.pop();

    // 计算结果并入栈
    int res = 0;
    if (p == '+') res = b + a;
    if (p == '-') res = b - a;
    if (p == '*') res = b * a;
    if (p == '/') res = b / a;
    num.push(res);
}

int main()
{
    string exp; cin >> exp;

    for (int i = 0; i < exp.size(); i++)
    {
        // 扫描到数字
        if (isdigit(exp[i]))
        {
            int x = 0, j = i;
            while (j < exp.size() && isdigit(exp[j]))
            {
                x = (x * 10 + exp[j]) - '0';
                j++;
            }
            num.push(x);
            i = j - 1;
        }
        // '(' 直接入栈
        else if (exp[i] == '(')
        {
            op.push(exp[i]);
        }
        // ')' 计算内容直到遇到匹配的 '('
        else if (exp[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop(); // 将 '(' 出栈
        }
        else
        {
            // 待入栈运算符优先级低（或相等）则先计算
            while (op.size() && h[op.top()] >= h[exp[i]]) eval();
            op.push(exp[i]);
        }
    }

    // 计算栈中剩余的
    while (op.size()) eval();

    cout << num.top() << endl;
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    单调栈

    单调栈用于寻找每个数左边第一个比它小（大）的数。

    题目：830. 单调栈 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10;

int stk[N], tt = 0;

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x; cin >> x;
        while (tt && stk[tt] >= x) tt--;
        cout << (tt ? stk[tt] : -1) << " ";
        stk[++tt] = x;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    单调队列

    单调队列用于求滑动窗口中的最大（小）值。

    题目：154. 滑动窗口 - AcWing题库

    #include 
const int N = 1e6 + 10;
int a[N], q[N]; // 队列中存的是下标

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int hh = 0, tt = -1; // 数组模拟队列
    // 单调递增队列
    for (int i = 0; i < n; i++)
    {
        // i - k + 1 滑动窗口头位置, q[hh] 窗口最小值的位置
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[i] <= a[q[tt]] ) tt--;
        q[++tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1; // 重置队列
    // 单调递减队列
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[i] >= a[q[tt]]) tt--;
        q[++tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }

    return 0;
}

    • 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
    • 34

    kmp

    略。。后面补。。

    Trie 树

    Trie 树用于快速存储和查找字符串集合的数据结构。

    // son[][] 存储当前节点的子节点的位置，分支最多 26 条
// cnt[] - 以当前点结尾的字符串个数（同时起标记作用）
// idx - 当前要插入的节点是第几个，每创建一个节点值 + 1
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];
}

    • 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

    Trie 字符串统计

    题目：835. Trie字符串统计 - AcWing题库

    AcWing 835. Trie字符串统计 - AcWing

    #include 
using namespace std;
const int N = 1e5 + 10;

// implement trie

int main()
{
    int n; cin >> n;
    char str[N];
    while (n -- )
    {
        char op;
        cin >> op >> str;
        if (op == 'I') insert(str);
        else if (op == 'Q') cout << query(str) << endl;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    最大异或对

    题目：143. 最大异或对 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10, M = 31 * N;

int a[N];
int son[M][2], idx;

void insert(int x)
{
    int p = 0;
    // 从高往低
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1; // 取 x 二进制第 i 位的值A
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (son[p][!u])
        {
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        insert(a[i]);
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    cout << res << endl;
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    并查集

    并查集：

    1. 将两个集合合并
    2. 询问两个元素是否在一个集合当中

    基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，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

    合并集合

    朴素并查集：

    // 存储每个节点的祖宗节点, 当 p[x] == x, 表示这个数就是祖宗节点
int p[N]; 

// 返回 x 的祖宗节点 + 路径压缩
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 将编号为 a 和 b 的两个数所在的集合合并
void merge(int a, int b)
{
	p[find(a)] = find(b);
}

// 编号 a 和 b 的两个数是否在同一个集合中
bool isSame(int a, int b)
{
	return find(a) == find(b);
}

// 初始化，假定节点的编号是 1 ~ n
void init()
{
	for (int i = 1; i <= n; i++) p[i] = i;
}

    • 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

    模板题：836. 合并集合 - AcWing题库

    参考：AcWing 836. 基础_并查集_合并集合java_python_c++ - AcWing

    路径压缩：

    #include 
using namespace std;
const int N = 1e5 + 10;

// implement union find

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

    // 初始化
	for (int i = 1; i <= n; i++) p[i] = i;

    while (m --)
    {
        char op;
        int a, b;
        cin >> op >> a >> b;

        if (op == 'M') merge(a, b);
        else puts(isSame(a, b) ? "Yes" : "No");
    }

    return 0;
}

    • 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

    连通块中点的数量

    模板：维护 size 的并查集

    // p[] 存储每个点的祖宗节点
// size[] 只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int p[N], size[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;
	size[i] = 1;
}

// 合并 a 和 b 所在的两个集合
size[find(b)] += size[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

    模板题：837. 连通块中点的数量 - AcWing题库

    #include 
using namespace std;
const int N = 1e5 + 10;

// p[i] i 的祖先节点
// nums[i] i 的连通块中点的数量
int p[N], nums[N];

// 查找 x 的祖宗节点 + 路径压缩
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    cin >> n >> m;
  
    // 初始化并查集
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        nums[i] = 1; // 默认只有一个点
    }

    while (m--)
    {
        int a, b;
        char op[2]; 
        cin >> op;
        if (op[0] == 'C')
        {
            cin >> a >> b;
            if (find(a) == find(b)) continue; // a b 已经在一个集合中
            nums[find(b)] += nums[find(a)];
            p[find(a)] = find(b); // 合并
        }
        else if (op[1] == '1')
        {
            cin >> a >> b;
            puts(find(a) == find(b) ? "Yes" : "No");
        }
        else if (op[1] == '2')
        {
            cin >> a;
            cout << nums[find(a)] << endl;
        }
    }
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    堆

    堆的常见操作：

    1. 插入一个数
    2. 求集合当中的最小值
    3. 删除最小值
    4. 删除任意一个元素
    5. 修改任意一个元素

    手写一个堆：

    // 1. 插入一个数
heap[++size] = x;
up(size);

// 2. 求集合当中的最小值
heap(1);

// 3. 删除最小值
heap[1] = heap[size];
size--;
down(1);

// 4. 删除任意一个元素
heap[k] = heap[size];
size--;
down(k);
up(k);

// 5. 修改任意一个元素
heap[k] = x;
down(k);
up(k);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    堆排序

    模板题：838. 堆排序 - AcWing题库

    细节：为了避免处理复杂的边界问题，h 数组下标从 1 开始
    则 2i 为左子树的下标，2i + 1 为右子树的下标

    #include 
using namespace std;
const int N = 1e5 + 10;

// h - 满足堆性质的数组
int h[N], siz;

// 从 u 往下调整，使得数组满足堆的性质
void down(int u)
{
    // t 存储三个节点中存在最小的下标，初始化为当前节点 u
    int t = u;
    if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2;
    if (u *2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    // t 进行了更新操作，则交换数组中的值并重新从当前 t 开始调整堆
    if (t != u)
    {
        swap(h[t], h[u]);
        down(t);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    // 读入乱序元素
    for (int i = 1; i <= n; i++) cin >> h[i];

    siz = n; // 初始化 size，表示堆里有 n 个元素
    // 把堆初始化成小根堆，从二叉树的倒数第二行开始，把数字大的下沉
    for (int i = n / 2; i; i--) down(i); 

    while (m --) 
    {
        cout << h[1] << " "; // 堆顶，最小值
        h[1] = h[siz--]; // 将最后一个元素挪到堆顶（相当于删除了最值元素）
        down(1); // 从头节点开始重新排列一遍，确保头节点是最小的
    }

    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    模拟堆 TODO

    哈希表

    哈希表：

    • 存储结构：开放寻址法、拉链法
    • 字符串哈希

    模拟散列表

    840. 模拟散列表 - AcWing题库

    拉链法：

    #include 
#include 
using namespace std;
const int N = 100003; // 大于数据范围的第一个质数

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

void insert (int x)
{
    // x % N + N 保证结果必为正数
    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;
}

int main()
{
    int n; cin >> n;
    memset(h, -1, sizeof h);

    while (n --)
    {
        char op;
        int x;
        cin >> op >> x;
        if (op == 'I') insert(x);
        else puts(find(x) ? "Yes" : "No");
    }
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37

    开放寻址法：

    #include 
#include 
using namespace std;

// 开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; // 大于数据范围的第一个质数
const int null = 0x3f3f3f3f; // 表示不存在数据，这个数不能在 x 范围内

int h[N];

// 寻找 x 存在的位置（已存在）或目标放置位置（不存在）
int find(int x)
{
    int k = (x % N + N) % N;
    while (h[k] != null && h[k] != x)
    {
        k++;
        if (k == N) k = 0; // 到底后从头开始
    }
    return k;
}

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

    while (n --)
    {
        char op;
        int x;
        cin >> op >> x;

        int k = find(x);
        if (op == 'I') h[k] = x;
        else puts(h[k] != null ? "Yes" : "No");
    }
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    字符串哈希

    题目：841. 字符串哈希 - AcWing题库

    #include 
#include 
#include 

using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 5;
// P = 131 或 13331 Q=2^64，在 99% 的情况下不会出现冲突
const int P = 131; // 131 13331 是经验值
// h[i] 字符串的哈希前缀和
ULL h[N], p[N];

// h[i] 前 i 个字符的 hash 值
// 字符串变成一个 P 进制数字，体现了字符 + 顺序，需要确保不同的字符串对应不同的数字
// 使用场景：两个字符串的子串是否相同
ULL query(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    int n, m;
    cin >> n >> m;
    string x;
    cin >> x;

    p[0] = 1;
    h[0] = 0;
    // 前缀和
    for (int i = 0; i < n; i++)
    {
        p[i + 1] = p[i] * P; // 预处理 P 进制
        h[i + 1] = h[i] * P + x[i]; // 前缀和求整个字符串的哈希值
    }

    while (m--)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        puts((query(l1, r1) == query(l2, r2) ? "Yes" : "No"));
    }

    cout << p << endl;
    return 0;
}

    • 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    STL

    STL 中常用容器：

    • vector，变长数组，倍增的思想（减少申请空间的次数，提高效率）
    • pair，存储一个二元组
    • string，字符串
    • queue，队列
    • priority_queue，优先级队列
    • stack，栈
    • deque，双端队列
    • set, map, multiset, multimap，基于平衡二叉树（红黑树），动态维护有序序列
    • unordered_set, unordered_map, unordered_multiset, unordered_multimap，哈希表
    • bitset，压位

    vector

    vector，动态数组
	size()
	empty()
	clear()
	front() / back()
	push_back() / pop_back()
	begin() / end()
	[] 支持像数组一样随机存储
	支持比较运算，按字典序 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    vecotr 的初始化：

    // 定义时初始化，容量为 10，初始值为 -1
vecotr<int> a(10, -1);

// 定义完再插入数据
vector<int> a;
for (int i = 0; i < 10; i++) a.push_back(i);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    vector 的遍历：

    // 遍历 1
for (int i = 0; i < a.size(); i++) cout << a[i] << ' ';
cout << endl;

// 遍历 2 - 迭代器，遍历时获取的是指针
for (auto i = a.begin(); i != a.end(); i++) cout << *i << ' ';
cout << endl;

// 遍历 3
for (auto x : a) cout << x << ' ';
cout << endl;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    vector 的比较运算符：

    // [3 3 3 3] < [4 4 4]
vector<int> a(4, 3), b(3, 4);
if (a < b) puts("a < b");

    • 1
    • 2
    • 3

    pair

    pair，二元对
	first 第一个元素
	second 第二个元素
	支持比较运算，以 first 为第一关键字，second 为第二关键字（字典序）

    • 1
    • 2
    • 3
    • 4

    自己手写一个结构体也能达到相同的效果，使用这个的好处就是节约代码

    pair 的初始化：

    // 使用 make_pair
pair<int, int> p1 = make_pair(1, 2);
// 直接使用 {}
pair<int, string> p2 = {20, "abc"};

    • 1
    • 2
    • 3
    • 4

    使用 pair 实现三元对：

    pair<int, pair<int, int>> p = {1, {2, 3}};

    • 1

    string

    string，字符串
	size() / length() 返回字符串的长度
	empty()
	clear()
	substr()
	c_str()

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    string a = "abcde";
cout << a.substr(1, 2) << endl; // bc
cout << a.substr(1) << endl; // bcde

    • 1
    • 2
    • 3
    string a = "hello ";
a += "world";
cout << a << endl; // hello world
printf("%s\n", a.c_str()); // 使用 printf 需要使用 c_str() 方法

    • 1
    • 2
    • 3
    • 4

    queue

    queue，队列
	size()
	empty()
	push() 向队尾插入一个元素
	pop() 弹出队头元素
	front() 返回队头元素
	back() 返回队尾元素

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    注意，queue 没有 clear() 函数，想要情况则直接重新构造一个 queue

    queue<int> q;
q = queue<int>(); // 相当于清空 queue

    • 1
    • 2

    priority_queue

    priority_queue，优先队列（默认大根堆）
	push() 插入一个元素
	top() 返回堆顶元素
	pop() 弹出堆顶元素

    • 1
    • 2
    • 3
    • 4

    priority_queue 也没有 clear()

    定义小根堆：

    priority_queue<int, vector<int>, greater<int>> heap;

    • 1

    其他技巧：插入元素时使用 -x，取出时再加个 -，则也相当于 小根堆：

    priority_queue<int> heap;
heap.push(-1);
heap.push(-2);
heap.push(-3);
cout << -heap.top() << endl; // 1

    • 1
    • 2
    • 3
    • 4
    • 5

    stack

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    deque

    deque，双端队列
	size()
	empty()
	clear()
	front() / back()
	push_back() / pop_back()
	push_front() / pop_front()
	begin() / end()
	[]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    deque 方法很多，但是效率比较慢，用的不是很多

    set

    set / multiset
	size()
	empty()
	clear()
	insert() 插入一个数
	find() 查找一个数
	count() 返回某一个数的个数
	erase()
		(1) 输入一个数 x，删除所有 x，复杂度 O(k + logn)
		(2) 输入一个迭代器，删除这个迭代器
	lower_bound() 最小上界，返回 >= x 的最小的数的迭代器
	upper_bound() 最大下界，返回 >x 的最小的数的迭代器 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    map

    map / multimap
	insert() 参数是一个 pair
	erase() 参数是 pair 或迭代器
	find()
	[] O(logn)
	lower_bound() / upper_bound()

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    map 用法和数组类似：

    map<string, int> m;
m["a"] = 1;
cout << m["a"] << endl;

    • 1
    • 2
    • 3
    unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表

和前面的 map set 类似，但是增删改查的时间复杂度是 O(1)
但是不支持 lower_bound() / upper_bound()，迭代器的 ++, --

    • 1
    • 2
    • 3
    • 4

    bitset

    bitset，压位
	bitset<10000> s;
	~, &, |, ^
	>>, <<
	==, !=
	[]
	count() 返回多少个 1
	any() 判断是否至少有一个 1
	none() 判断是否全为 0
	set() 把所有位置成 1
		set(k, v) 将第 k 位变成 v
	reset() 将所有位置成 0
	flip() 等价于 ~
		flip(k) 第 k 位取反 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    【Mysql】——索引的深度理解
    g++ 命令
    2023-10-08 mysql-代号m-增加外键导致crash-问题分析
    解决charles只能使用30分钟
    zynq实现视频动态字符叠加OSD，提供2套工程源码和技术支持
    澳洲猫罐头如何？我亲自喂养过的优质猫罐头分享
    动态规划：较小集合的累加和 + 限制集合中数字的个数
    记一次dump文件分析历程
    C函数学习总结
    通达信高级使用:预先筛选股票池进行预警选股
  • 原文地址：https://blog.csdn.net/weixin_43734095/article/details/126268612