AcWing算法基础课笔记 ------ 第二章 数据结构

���篇记录一下AcWing上第二章的笔记，这一章收获也很多，学会了用数组去模拟链表，复习了一遍KMP，求表达式，以及新的一些数据结构，字典树，并查集，还有更为高效的哈希表。

文章目录

• 一. 单链表
• 二. 双链表
• 三. 栈
• • 1. 表达式求值
  • 2. 单调栈
  • 四. 队列
  • • 1. 滑动窗口求最大值和最小值
    • 五. KMP算法
    • 六. 字典树
    • 七. 并查集
    • 八. 堆
    • 九. 哈希表
    • • 1. 开放寻址法
      • 2. 拉链法
      • 3. 字符串哈希

        一. 单链表

        以前学习的单链表是写一个结构体出来，一个是val，另一个是指针，然后用malloc动态的开辟空间，一直newnode。

        而在本讲中是利用数组来模拟实现一个单链表。

        其实万变不离其宗，对于链表的增删查改操作其实都是一个意思。

        就比如在链表中的头插是下面这个样子:

        //AddHeadnewnode = BuyNode(val);newnode -> next = head -> next;head -> next = newnode;//Delete 可以删除cur 所指向的下一个节点cur -> next = cur -> next -> next;

        而数组中的是：

        //AddHeaddata[idx] = val;//这一步就是BuyNodenext[idx] = head;//链接头节点的head = idx++;////Delete 删除cur后面的节点next[cur] = next[next[cur]].

        在本讲中是用一个题来更好的帮助理解单链表。

        题目中的三个函数对应着增和删。

        题目链接

        下面是整体的代码:

        #include #define N (100000 + 10)//单链表：//head 头节点//idx 下一个位置的下标，也即是newNode的位置。//data 数据//next 下一个位置的指针int data[N],next[N],idx,head;//初始化void Init(){    head = -1, idx = 0;}//头插void AddHead(int val){    data[idx] = val, next[idx] = head, head = idx++;}//在k的下一个位置插入void Insert(int k,int val){    data[idx] = val, next[idx] = next[k], next[k] = idx++;}//删除k的下一个节点void Delete(int k){    next[k] = next[next[k]];}int main(){    int n,i;    scanf("%d",&n);    //    Init();    while(n--)    {        int val,k;        char oper;        scanf(" %c",&oper);        if(oper == 'H')        {            scanf("%d",&val);            AddHead(val);        }        else if(oper == 'I')        {            scanf("%d%d",&k,&val);            Insert(k - 1,val);        }        else        {            //Delete            scanf("%d",&k);            if(k == 0)                head = next[head];                        Delete(k-1);        }                }            for (i = head; i != -1; i = next[i])    {        printf("%d ",data[i]);    }            return 0;}

        二. 双链表

        双链表呢就是说每个节点有两个指针和数据组成，prev指向前一个节点，next指向下一个节点。

        • 对于双链表来说其实也和用结构体定义的那种指针方式是一样的，只要直到其增删查改的原理，换成数组也是一样的，只是表达方式不一样，额以前学习知识的时候，老师经常所说的换汤不换药就是这么个道理
        • 要注意的是，用数组模拟链表的话，我们将0位置当head，1位置当tail
        • 所以最开始初始化的时候可以先将0和1链接起来相当于一个空表，然后inx从2开始就好了
        • add操作 — 在第k个节点的下一个位置插入新节点
        • data[idx] = val, next[idx] = next[k],prev[idx] = k,新节点的操作
        • prev[next[k]] = idx,next[k] = idx; 重新链接新节点的操作。
        • Delet — 删除第k个节点。

          因为idx从下标为2的位置开始，所以调用链表函数的时候，需要将所有的k转化成k+1.

          #include #include #define N 100000int prev[N],data[N],next[N];int idx;void Init(){    next[0] = 1, prev[1] = 0;    //此注释打开即可模拟处循环链表。    //prev[0] = 1, next[1] = 0;    idx = 2;}//在第k个元素的下一个位置插入一个数void Add(int k, int val){    //newnode 的操作    data[idx] = val;    next[idx] = next[k];    prev[idx] = k;        //重新链接    prev[next[k]] = idx;    next[k] = idx;    idx++;}//删除k的下一个节点void Delete(int k){    next[prev[k]] = next[k];    prev[next[k]] = prev[k];}int main(){    int n,i;    scanf("%d",&n);        Init();        while(n--)    {        char op[5];        int x,k;        scanf("%s",op);        if(!strcmp(op,"L"))        {            scanf("%d",&x);            Add(0,x);        }        else if(!strcmp(op,"R"))        {            scanf("%d",&x);            Add(prev[1],x);        }        else if(!strcmp(op,"D"))        {            scanf("%d",&k);            Delete(k + 1);        }        else if(!strcmp(op, "IL"))        {            scanf("%d%d",&k,&x);            Add(prev[k + 1],x);        }        else        {            scanf("%d%d",&k,&x);            Add(k + 1, x);        }    }    //printf("head: %d %d\n",prev[0],next[0]);    //printf("tail :%d %d\n",prev[1],next[1]);    for (i = next[0]; i != 1; i = next[i]) printf("%d ",data[i]);        return 0;}

          三. 栈

          栈和队列也都是用数组可以模拟出来，嘿，嘿，这个我熟，C语言刷题每次遇到栈，只能手写一个，不过也不费什么时间，这个看个人习惯吧，我是习惯于从1开始放数据，然后top = 0，就是栈空。

          这个代码是我每次用栈的方式

          int stk[N];int top = 0;//pushstk[++top];//poptop--;//getTop//获取栈顶元素stk[top];//isemptytop == 0 ?;

          下面看看一道经典的题目把，求一个表达式的值。

          1. 表达式求值

          在leetcode上做过类似的题目，但是都没有这个全面，以前做过一道只有+ -的，还有只有+ -然后包含括号的等等。

          这次的题目是 + - * / 然后包含括号。

          • 首先需要两个栈，一个存放操作符号，还有一个存放数。
          • 在遍历字符串的时候又有一下几种情况
            1. s[i] 是数字的话，就把它的num求出来，记得更新 i 的位置
            2. 如果是（ 啥也不干，入栈就好了
            3. 如果是 ） 就说明改出栈，因为不管什么优先级，都应该先算括号里面的数。
            4. 最后就是4中操作符的情况，要注意，如果新的操作符需要入栈时候，判断栈顶的操作符的优先级是否大于等于需要入栈的操作符，如果大于等于的话，那么就先对当前栈顶进行操作，然后再入栈。

            #include #include #include #include #define N (100000 + 10)int stkNums[N];char stkOper[N];int operTop,numsTop;void eval(){    int y = stkNums[numsTop--];    int x = stkNums[numsTop--];    char op = stkOper[operTop--];        int ans = 0;        if(op == '+') ans = x + y;    else if(op == '-')  ans = x - y;    else if(op == '*')  ans = x * y;    else if(op == '/')  ans = x / y;        stkNums[++numsTop] = ans;    }int main(){    //操作符优先级    int map[50];    map['+'] = 1,map['-'] = 1,map['*'] = 2,map['/']= 2;        //读入表达式    char s[N];    scanf("%s",s);        int len = strlen(s);    int i;    //遍历表达式    for (i = 0; i = map[s[i]])            {                eval();            }            stkOper[++operTop] = s[i];        }    }        while(operTop != 0)    {        eval();    }    printf("%d\n",stkNums[numsTop]);    return 0;}

            2. 单调栈

            单调栈就是是一个栈呈单调递增或者递减的形式维护，然后利用整个栈就得到想要的结果，题目关于求 " 下一个更大的……" 这类题目。

            下面是一道求解左边第一个更小的数据，没有的话打印-1.

            • 我们用一个单调递增的栈维护。
            • 这样子在入栈的时候栈顶的元素就是左边第一个比子小的元素。
            • 如果栈为空，就说明自己最小，使其出栈出完了，或者说是自己处于边界，这类情况打印-1就好了。

              #include #define N 100010int stk[N],top;int main(){    int i,n,x;    scanf("%d",&n);    for (i = 0; i = x)        {            top--;        }                if(top == 0)            printf("-1 ");        else            printf("%d ",stk[top]);                stk[++top] = x;            }            return 0;}

              四. 队列

              队列也可以用数组来模拟，前些天还在刷单调队列的，当然每个人模拟队列的方式是不同的，看自己习惯吧。

              下面是我用数组模拟的队列的方式：

              int que[N];int front = 0, rear = 0;//pushque[rear++];//popque[front++];//不仅能获取队首，还能获取队尾que[front]; //队首que[rear - 1];//队尾//isemptyfront == rear ? 

              那队列中也有一种叫单调队列的东西，还有一种叫做优先队列但是也可以叫做堆，堆又跟树有关系了，在这里就先不说优先队列（堆）了，先看单调队列吧。

              • 单调队列和单调栈是一样的，都是维护其单调递增减，只是push和pop的操作方式不一致

                而单调队列应用最多的就是在滑动窗口这种算法中。

                1. 滑动窗口求最大值和最小值

                该题也是AcWing上面的题目，链接在这里。

                这道题我之前也做过，在之前的文章中也有，所以这里就不太细的展开叙述了，总体思路是一样的，只是人家的更简洁。

                链接

                • 我之前的代码中是利用两个指针left 和 right 来指向窗口的边界，然后每次更新窗口的时候获取当前窗口的答案
                • 而下面的代码中则是只要i > k - 1,就获取结果，更新窗口边界的条件变成了
                • i - k + 1 > que[front] 于我之前的 right - left + 1 > k 不同。

                  #include #define N 1000010int que[N], front, rear;int nums[N];int main(){    int i, j, n, k;    scanf("%d%d",&n,&k);    for (i = 0; i  que[front]) front++;                while(front != rear && nums[que[rear - 1]] >= nums[i]) rear--;                que[rear++] = i;        if(i >= k - 1)        {            printf("%d ",nums[que[front]]);        }    }    printf("\n");        //最小值    front = 0, rear = 0;    for (i = 0; i  que[front]) front++;                while(front != rear && nums[que[rear - 1]] = k - 1)        {            printf("%d ",nums[que[front]]);        }    }    printf("\n");            return 0;}

                  五. KMP算法

                  kmp算法从学到至今，每每想起来都是痛苦的，很难，但是本讲中，y总讲的还是非常的清楚了，感觉比之前自己琢磨的有深入了一点，知识嘛，总是后面的每一遍都会比其前面有着不一样的收获。

                  子串和主串的下标都是从1开始。

                  • 咱先抛开next数组不说，就单纯的说一下kmp匹配的思想是什么。
                  • 利用两个指针，i和j分别指向主串str 与 子串 subStr, 注意 j 可以取成0或者是1.
                  • 那么相应的往回倒退的时候，就需要j = next [j] || j = next[j - 1]两种中的其一。
                  • 我在此采取 j = 0， 然后利用 j = next [j] 的方式进行回退.
                  • 然后取遍历子串和主串，如果在当前位置上遇到的字符不同，那么j需要采取倒退的方式去，直到遇到相同的字符，或者说 j = 0，退到起点的位置，就不需要去倒退了。
                  • 否则的话就是str[i] == str[ j + 1] ，然后 j ++ 指向下一个就好了
                  • 但要注意的是 如果 j == 子串大小，就说明找完了，匹配成功就可以进行相应的操作。
                  • 比如说返回其起始位置，还有返回 true || false 表示是否存在此子串等等，看具体的应用场景即可。

                    代码如下：

                    //m 代表主串长度，n代表子串长度 ， str 和 substr都从1开始存储for (i = 1, j = 0; i while (j != 0 && str[i] != subStr[j + 1]){//回退j = next[j];}if (str[i] == subStr[j + 1]){j++;}if(j == n){//匹配成功，具体操作看应用场景。//如果看看有多少个子串，回退一下即可//j = next[j];}}while (j != 0 && subStr[i] != subStr[j + 1]){j = next[j];}if (subStr[i] == subStr[j + 1]){j++;}//next[i] = j;}    int n,m;    scanf("%d%s%d%s",&n,subStr + 1,&m,str + 1);        int i,j;    //next数组    for (i = 2, j = 0; i         while(j != 0 && subStr[i] != subStr[j + 1]) j = next[j];        if(subStr[i] == subStr[j + 1])  j++;                next[i] = j;    }        //kmp    for (i = 1, j = 0; i         while(j != 0 && str[i] != subStr[j + 1])    j = next[j];        if(str[i] == subStr[j + 1]) j++;                if(j == n)        {            printf("%d ", i - n);            j = next[j];        }    }        return 0;}    int r = 0; // root  根节点    int i;    for (i = 0; s[i]; i++)    {        int u = s[i] - 'a';        if(son[r][u] == 0)        {            //字母不存在，需要进行插入            son[r][u] = ++idx;        }                //迭代下去        r = son[r][u];    }        cnt[r]++;}int TrieFind(char *s){    int r = 0;    int i;    for (i = 0; s[i]; i++)    {        int u = s[i] - 'a';        if(son[r][u] == 0)        {            return 0;        }                r = son[r][u];    }        return cnt[r];}void TrieDelete(char* s){int r = 0;int i;for (i = 0; s[i]; i++){int u = s[i] - 'a';if(son[r][u] == 0){//无此节点 return;}r = son[r][u]; }if(cnt[r] != 0){cnt[r]--;}}int main(){    int n;    scanf("%d",&n);    while(n--)    {        char op,s[N];        scanf(" %c%s",&op,s);        if(op == 'I')        {            TrieAdd(s);        }        else if (op == 'D')         {        TrieDelete(s);}        else        {            printf("%d\n",TrieFind(s));        }    }        return 0;}if (p[x] != x){p[x] = find(p[x])}return p[x];}//合并操作就是将自己的父亲节点连接到另一个集合的根节点上就好了。p[find(x)] = find(y);    if(p[x] != x)        p[x] = Find(p[x]);        return p[x];}bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination){    int i;    //初始化p数组    for (i = 0; i