算法基础课-数据结构

算法基础课

数据结构

单链表

=#include <iostream>

using namespace std;

const int N = 100010;


/*这个题的理解上有一个问题困扰了我很久，就是这个Idx究竟代表什么，翻了很多的评论，我觉得以下这个评论
我觉得很合适说说的我个人对idx的理解
先区分两个概念：
节点和结点
节点：一个点
结点：链表的元素，含e[idx],ne[idx]两个部分
e[idx]:结点编号为idx对应的节点值
ne[idx]：结点编号为idx对应的下一个结点的编号
区分完这两个概念应该能理解idx的作用，为结点编号
我觉得看完这个之后，应该就能很好的理解这个代码
*/

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

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

双链表

#include <iostream>

using namespace std;

const int N = 100010;


/*
这个题目，初始的时候我看的有点懵逼，在这个模板里，加了两个哑巴结点，这样就能够减少操作，实际上0和1这个结点一直不会被删除，是一个很好的做法
*/
int m;
int e[N], l[N], r[N], idx;

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

int main()
{
    cin >> m;

    // 0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;

    while (m -- )
    {
        string op;
        cin >> op;
        int k, x;
        if (op == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            insert(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';//输出的时候也是从r[0]输出，没有输出哑巴结点
    cout << endl;

    return 0;
}

栈

模拟栈

#include <iostream>
using namespace std;
const int N = 100010;
int st[N];
int top = -1;
int n;
int main()
{
    cin >> n;
    while(n--)
    {
        string s;
        cin >> s;

        //栈顶所在索引往后移动一格，然后放入x。
        if(s == "push")
        {
            int a;
            cin >> a;
            st[++top] = a;
        }

        //往前移动一格
        if(s == "pop")
        {
            top --;
        }
        //返回栈顶元素
        if(s == "query")
        {
            cout << st[top] << endl;
        }
        //大于等于 0 栈非空，小于 0 栈空
        if(s == "empty")
        {
            cout << (top == -1 ? "YES" : "NO") << endl;
        }
    }
}

表达式求值

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
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 r = 0;//结果 

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))//数字入栈
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            //这个地方的理解可以看看海绵宝宝题解的第一条评论，写的很好
            num.push(x);//数字入栈
            i = j - 1;
        }
        //左括号无优先级，直接入栈
        else if (s[i] == '(')//左括号入栈
        {
            op.push(s[i]);
        }
        //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

队列

模拟队列

#include <iostream>
using namespace std;
const int N = 100010;
int q[N];

//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;

//入队：队尾先往后移动一格，再放入要插入的数据
void push(int x){
    q[++tt] = x;
}
//出队：队头往后移动一格
void pop(){
    hh++;
}
//[hh, tt]表示队列区间，当tt >= hh时，区间不为空
void empty(){
    if(tt >= hh) cout << "NO" << endl;
    else cout << "YES" << endl;
} 
//hh指向队头，q[hh]代表队头元素
void query (){
    cout << q[hh] << endl;
}

int main(){
    cin >> m;
    while(m--){
        cin >> s;
        //入队
        if(s == "push"){
            int x;
            cin >> x;
            push(x);
        }
        //出队
        if(s == "pop"){
            pop();
        }
        //问空
        if(s == "empty"){
            empty();
        }
        //问队头
        if(s == "query"){
            query();
        }
    }
}

单调栈

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[ ++ tt] = x;
    }

    return 0;
}

单调队列

#include <iostream>
using namespace std;
const int N = 1000100;

//这段代码中很关键的点在于，q[N]中存的是数组下标，而不是数组元素
//单调队列一般用双端队列保证其单调性
int a[N], q[N], n, k;
//队头和队尾，在队尾插入，队头获取
int front = 0, tail = -1;


int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    //先找每个窗口的最小值
    for (int i = 0; i < n; i++) {
        //如果当前队头在数组的下标小于当前窗口的最小下标，这个窗口就不包含这个元素了那么无论如何都要剔除队头这个元素
        //所以要在队头删除这个元素
        if (front <= tail && i - k + 1 > q[front]) front++;
        //保证单调性，在队尾删除（为什么要在队尾删除，简单来说在队头删除不能保证单调
        //比如-3 5为当前队列，当前的元素为3，如果在队头操作，那么按照a[i] <= a[q[front]，有3 > -3，因此不做删除操作
        //但是接下来就出现问题了，3就要入队了。此时队列就是-3 5 3，不符合单调性了！
        //但如果在队尾操作，按照a[i] <= a[q[tail]，有3 < 5，就要让5出队
        //之后3入队，队列就是-3 3，满足单调性
        while (front <= tail && a[i] <= a[q[tail]]) tail--;
        q[++tail] = i;
        //队头为窗口的最小值
        if (i >= k - 1) printf("%d ", a[q[front]]);
    }
    printf("\n");
    //这次找最大值，同理
    front = 0, tail = -1;
    for (int i = 0; i < n; i++) {
        if (front <= tail && i - k + 1 > q[front]) front++;
        while (front <= tail && a[i] >= a[q[tail]]) tail--;
        q[++tail] = i;
        if (i >= k - 1) printf("%d ", a[q[front]]);
    }
}

KMP

//这段代码我还有很多没明白的地方，回头看看算法笔记
#include <iostream>
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    //求next数组
    for (int i = 2, j = 0; i <= n; 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 <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

Trie (专门用来处理存储字符串的集合问题)

Trie字符串统计

#include <iostream>

using namespace std;

const int N = 100010;

//trie树专门用来处理存储字符串的集合问题，如果还是有不懂的地方，参照这篇博客
//https://blog.csdn.net/raelum/article/details/128885107

int son[N][26], cnt[N], idx;
char str[N];

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 == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

最大异或对

#include <iostream>
#include <algorithm>

//有不懂的地方，看这篇博客https://blog.csdn.net/raelum/article/details/128885107
using namespace std;

const int N = 100010, M = 3100010;

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

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int &s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int s = x >> i & 1;
        if (son[p][!s])
        {
            res += 1 << i;//这是等于加上2^i次方
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

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

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));

    printf("%d\n", res);

    return 0;
}

并查集

合并集合

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];//建立一个父结点数组


int n,m;

int find(int x)//find函数，路径压缩
{
    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 -- )
    {
        int a,b;
        char op[2];//两个操作
        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;
}

连通块中点的数量

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N],cnt[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        p[i]=i;
        cnt[i]=1;
    }
    while (m -- )
    {
        string op;
        cin>>op;
        int a,b;
        if(op=="C")
        {
            cin >> a>>b;
            a=find(a),b=find(b);
            if(a!=b)
            {
                p[a]=b;
                cnt[b]+=cnt[a];
            }
        }
        else if(op=="Q1")
        {
            cin >> a>>b;
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else 
        {
            cin >> a;
            int x=find(a);
            cout << cnt[x]<<endl;
        }
    }
    return 0;
}

食物链、

#include <iostream>

using namespace std;

const int N = 1e5 + 10;


//这个算法的关键是划分集合,，用距离来判断是否属于同一类，思路实在是很绝，来判断是不是真话，如果有疑问，可以看yxc代码的评论区

int n, m;
int p[N], d[N]; //p[]寻找祖宗节点，d[]求到祖宗节点的距离

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]); // u暂时存一下p[x]根节点，辅助变量
        d[x] += d[p[x]];    // 更新距离
        p[x] = t;
    }
    return p[x];
}


// 不行，因为这个路径的长度（高度），是需要自上而下加起来的，从根节点往下走
// 所以要先调用递归

// int find(int x)
// {
//     if (p[x] != x)
//     {
//         d[x] += d[p[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;

    int res = 0;//记录错误数
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ; // 当前的话中X或Y比N大，是假话
        else
        {
            int px = find(x), py = find(y); // 查找根节点
            if (t == 1) // 判断是否同类
            {
                if (px == py) {  // 若 x 与 y 在同一个集合中
                    if ((d[x] - d[y]) % 3) res ++ ; // 两数到根节点距离之差的模不为 0，说明不是同一类，是假话
                    // 其中 (d[x] - d[y]) % 3 不可写为 d[x] % 3 != d[y] % 3
                    // 因为 d[x], d[y] 可能为负数（一正一负），可改做 (d[x] % 3 + 3) % 3 != (d[y] % 3 + 3) % 3
                    // 负数 mod 正数为负数
                } else {    // 则 x 与 y 不在同一个集合中
                    p[px] = py;     // x 所在集合 合并到 y 所在集合
                    d[px] = d[y] - d[x];//这里是先把所有的存到一个集合里的意思，认定没出现在集合里的第一句话为真话
                    // d[x] 的距离为什么不更新？
                    // 只是暂时不更新，在调用 find 时再更新
                }
            }
            else // X 是否吃 Y
            {
                if (px == py) {     // 若 x 与 y 在同一个集合中
                    // 若 X 吃 Y，则 d[x] 比 d[y] 大 1
                    if ((d[x] - d[y] - 1) % 3) res ++ ;  // 若距离之差 - 1 的模不为 0，说明吃不掉，是假话
                } else {    // 则 x 与 y 不在同一个集合中
                    p[px] = py;
                    // (d[x] - d[y] - 1) % 3 == 0
                    // d[x] + d[px] - 1 = d[y]  则：
                    d[px] = d[y] + 1 - d[x];//这里和上面一样
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

堆

堆排序

#include <iostream>
#include <algorithm>

//详细的内容看这个链接：https://www.acwing.com/solution/content/120483/
//以及这个链接：https://raelum.blog.csdn.net/article/details/128800503

using namespace std;

const int N = 100010;

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

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)
    {
        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]);
    cnt = n;
    for (int i = n / 2; i; i -- ) down(i);//这样就构建成了一个小根堆
    while (m -- )
    {
        printf("%d ", h[1]);//初始时这个h[1]为什么是最小值
        h[1] = h[cnt -- ];
        down(1);
    }

    puts("");

    return 0;

}

模拟堆

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int heap[N], cnt;
int ph[N];  // 记录第k个插入的元素的下标(次序->下标)
int hp[N];  // 记录当前元素下标对应元素插入的次序(也就是第几个插入的 下标->次序)


/*
    原来交换是直接交换堆中的两个元素，但是本题需要对第k个插入的数修改，
    所以我们需要一个数组ph来存储第k次插入的元素的下标，所以当我们交换两个元素时，
    存储下标的数组对应位置也需要交换，从而保证第k次插入的元素与其下标对应。
    然而由于交换操作传入的是两个元素在堆中的下标，若我们要交换下标记录数组ph数组中对应的下标，
    则需要知道这两个元素是第几个插入的，所以我们需要一个hp数组来存放下标对应元素的插入次序，
    于是当我们交换两个元素时，存储数组元素插入次序的对应位置也需要交换，
    从而保证当前下标对应的元素与其插入次序对应。

*/
void heap_swap(int a, int b) {
    // 注意不能改为swap(a, b)，因为我们是要将数组ph中保存的两元素的下标进行交换，否则数组ph中的位置并未改变。
    swap(ph[hp[a]], ph[hp[b]]);  // 先由hp找到对应的插入次序，然后交换ph数组中记录的两个元素的下标
    swap(hp[a], hp[b]);         // 交换hp数组中记录的两个元素的插入次序
    swap(heap[a], heap[b]);    // 最后交换堆中的两个元素
}

void downAdjust(int u) {
    int m = u;
    if (u * 2 <= cnt && heap[u * 2] < heap[m]) m = u * 2;
    if (u * 2 + 1 <= cnt && heap[u * 2 + 1] < heap[m]) m = u * 2 + 1;

    if (u != m) {                   // 如果当前结点不为最小结点
        heap_swap(u, m);
        downAdjust(m);
    }
}

void upAdjust(int u) {
    while (u / 2 && heap[u / 2] > heap[u]) {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main() {
    int index = 0;                  // 记录每个元素插入的次序 
    int n = 0;
    cin >> n;

    while (n--) {
        string op;
        cin >> op;

        int x, k;
        if (op == "I") {            // 插入一个数x
            cin >> x;
            cnt++;
            index++;                // 记录当前元素是第几次插入的
            ph[index] = cnt;        // 堆尾插入，故第index次插入的元素下标为cnt
            hp[cnt] = index;        // 当前下标为cnt的元素为第index次插入
            heap[cnt]=x;            // 记录插入的值(即heap[ph[index]] = x)
            upAdjust(cnt);          // 从堆尾向上调整
        } else if (op == "PM") {    // 输出当前集合中的最小元素
            cout << heap[1] << endl;
        } else if (op == "DM") {    // 删除当前集合中的最小值
            heap_swap(1, cnt);      // 将堆头元素与堆尾元素交换
            cnt--;
            downAdjust(1);
        } else if (op == "D") {     // 删除第k个插入的数
            cin >> k;
            /*
                为什么需要用pos保存第k次插入元素的下标？
                因为当我们执行完heap_swap(pos, cnt)操作后，第k次插入元素的下标会变成cnt(即ph[k] = cnt)，
                而我们需要调整的是交换后的原来cnt位置上的元素(其下标变为了pos)，所以需要保存下来。
            */
            int pos = ph[k];        // 由插入次序得到在堆中的下标
            heap_swap(pos, cnt);    // 将第k个插入的数与堆尾元素交换
            cnt--;                  // 堆容量减一
            upAdjust(pos), downAdjust(pos);  
        } else if (op == "C") {     // 修改第k个插入的数，将其变为x 
            cin >> k >> x;
            int pos = ph[k];        // 得到第k个插入的元素的下标
            heap[pos] = x;          // 修改第k个插入的数
            upAdjust(pos), downAdjust(pos);
        }
    }

    return 0;
}

哈希表

模拟散列函数

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200003, null = 0x3f3f3f3f;

int h[N];


//find 函数实现了开放寻址法的线性探测。首先计算哈希值 t，然后循环查找直到找到空位置或者找到目标值 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;
}

int main()
{
    memset(h, 0x3f, sizeof h);//用 `memset` 函数将数组 `h` 中的所有元素初始化为 `0x3f3f3f3f`，即 `null`。

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

字符串哈希

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

//可以仔细看这两个链接：https://www.acwing.com/solution/content/24738/
//https://www.acwing.com/solution/content/205524/
// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
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;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P; //求p的多少次方用的，比如p[i]就是p的i次方          
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
        //假设字符串为“123”，那h[2]=(1p^2+2p^1+3p^0) 又等于h[1]p+s[2] 即 (1p^1+2p^0)p+3,这里的123其实实际上不是数字，是用它的ASSIC码计算，为了方便理解才直接用数字
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}