数据结构基础11月23日

wangzilong913 · 2024-11-23 17:19:35 · 个人记录

~~又是被迫写总结的一天啊！！~~

1.栈 stack

栈的定义

栈是一种 后进先出 的线性数据结构，我们可以用数组与一个变量（栈顶元素）和STL中的 stack进行实现。

栈的用途

1.表达式计算

依靠栈后进先出的特点，我们可以用其来做算数表达式的计算

中缀表达式转后缀表达式

建立一个用于存运算符的栈，逐一扫描该中缀表达式中的元素。

（1）如果遇到一个数，输出该数。

（2）如果遇到左括号，将其入栈。

（3）如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈。

（4）如果遇到运算符，只要栈顶元素的优先级不低于新符号，就不断取出栈顶并输出， 最后把新符号进栈。
依次取出并输出栈中的所有剩余符号，最终输出的序列就是一个与原中缀表达式等价的后缀表达式。

后缀表达式求值

建立一个用于存数的栈，逐一扫描该后缀表达式中的元素。（1）如果遇到一个数，将其入栈。

（2）如果遇到运算符，就取出栈顶的两个数进行计算，把结果入栈。
扫描完成后，栈中只剩下一个数，即最终结果。

2.括号匹配

利用栈后进先出的特性，将最近的左括号与右括号 "消掉"。

最后再判断栈是否为空。

3.单调栈

有一种特殊的栈，单调栈。即维护栈内元素递增或递减，及时排除不可能的选项，保持策略集合的高度有效性和秩序性。 对于某些有特殊性质的题，用单调栈可以极大的优化时间复杂度。

栈的典型例题

1. 表达式计算4

一道栈的综合题，可以分为三步来做：

去多余括号
转为后缀表达式
计算后缀表达式

还有三个易错点：

首尾加括号防越界
多位数的存储
负号的解决方式

Ac code

#include <bits/stdc++.h>
using namespace std;
stack <int> stk0;
stack <char> stk1;
stack <int> stk2;
map <char,int> m;
string s1;
char c1[1000005];
int j,k;
int main(){
    m['+'] = m['-'] = 1;
    m['*'] = m['/'] = 2;
    m['^'] = 3;
    cin>>s1;
    s1 = '(' + s1 + ')';
    for(int i = 0;i <= s1.size();i++){
        if(s1[i] == '('){
            stk0.push(i);
        }
        else if(s1[i] == '('){
            if(s1.empty()){
                s1.erase(i,1);
                i--;
            }
            else{
                stk0.pop();
            }
        }
    }
    for(int i = 0;i <= s1.size();i++){
        if(s1[i] == '(' && s1[i+1] == '-'){
            s1.insert(i+1,"0");
        }
    }
    for(int i = 0;i < s1.size();i++){
        char c = s1[i];
        if(c <= '9' && c >= '0'){
            j++;
            c1[j] = c;  
            if(s1[i+1] <= '9' && s1[i+1] >= '0'){
                j++;
                c1[j] = '.';
            }
        }
        else if(c == '('){
            stk1.push(c);
        }
        else if(c == ')'){
            while(!stk1.empty() && stk1.top() != '('){
                j++;
                c1[j] = stk1.top();
                stk1.pop();
            }
            stk1.pop();
        } 
        else{
            while(!stk1.empty() && m[stk1.top()] >= m[c] && stk1.top() != '('){
                j++;
                c1[j] = stk1.top();
                stk1.pop();
            }
            stk1.push(c);
        }
    }
    while(!stk1.empty()){
        j++;
        c1[j] = stk1.top();
        stk1.pop();
    }
//  for(int i = 1;i <= j;i++){
//      cout<<c1[i];
//  }
//  cout<<endl;
    for(int i = 1;i <= j;i++){
        if(c1[i] <= '9' && c1[i] >= '0'){
            k = k*10 + (c1[i]-'0');
            if(c1[i+1] != '.'){
                stk2.push(k);
                k = 0;
            }
        }
        else if(c1[i] == '+'){
            int a,b;
            a = stk2.top();
            stk2.pop();
            b = stk2.top();
            stk2.pop();
            stk2.push(b+a);
        }
        else if(c1[i] == '-'){
            int a,b;
            a = stk2.top();
            stk2.pop();
            b = stk2.top();
            stk2.pop();
            stk2.push(b-a);
        }
        else if(c1[i] == '*'){
            int a,b;
            a = stk2.top();
            stk2.pop();
            b = stk2.top();
            stk2.pop();
            stk2.push(b*a);
        }
        else if(c1[i] == '/'){
            int a,b;
            a = stk2.top();
            stk2.pop();
            b = stk2.top();
            stk2.pop();
            stk2.push(b/a);
        }
        else if(c1[i] == '^'){
            int a,b;
            a = stk2.top();
            stk2.pop();
            b = stk2.top();
            stk2.pop();
            stk2.push(pow(b,a));
        }
    }
    cout<<stk2.top();
    return 0;
}

2. Largest Rectangle in a Histogram

单调栈的板子题，首先建立一个栈，用来保存若干个矩形，这些矩形的高度是单调递增的。我们从左往右依次扫描每个矩形。

如果当前矩形比栈顶矩形高，直接进栈。

否则不断取出栈顶，直至栈为空或栈顶矩形的高度比当前矩形小。在出栈过程中，我们累计被弹出的矩形的宽度之和，并且每弹出一个矩形，就用它的高度乘上累计的宽度去增加更新答案。

Ac code

#include <bits/stdc++.h>
using namespace std;
long long n,h[400000],l[400005],r[400005],ans;
stack <long long> st;
int main(){
    while(cin>>n){
        if(n == 0){
            break;
        }
        while(1){
            if(st.empty())
                break;
            st.pop();
        }
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(h,0,sizeof(h));
        for(int i = 1;i <= n;i++)
            cin>>h[i];
        l[1] = 1;
        r[n] = 1;
        for(int i = 1;i <= n;i++){
            if(st.empty()){
                st.push(i);
                continue;
            }
            while(1){
                if(st.empty())
                    break;
                if(h[st.top()] < h[i])
                    break;
                st.pop();
            }
            if(!st.empty())
                l[i] = i - st.top();
            else
                l[i] = i;
            st.push(i);
        }
        while(1){
            if(st.empty())
                break;
            st.pop();
        }
        for(int i = n;i >= 1;i--){
            if(st.empty()){
                st.push(i);
                continue;
            }
            while(1){
                if(st.empty()){
                    break;
                }
                if(h[st.top()] < h[i]){
                    break;
                }
                st.pop();
            }
            if(!st.empty()){
                r[i] = st.top() - i;
            }
            else{
                r[i] = n - i + 1;
            }
            st.push(i);
        }
        ans = 0;
        for(int i = 1;i <= n;i++)
            ans = max(ans,(l[i]+r[i]-1)*h[i]);
        cout<<ans<<endl;
    }
    return 0;
}

2.队列

队列的定义

队列是一种先进先出的线性数据结构。

一般来说，元素从右端进入队列，从左端离开队列，于是我们称队列的左端为队头，右端为队尾。

可以用数组和两个变量（分别指向队头与队尾）与STL中的 queue实现队列。

队列的用途

1. 队列的变体

（1）优先队列 priority_queue

优先队列是给每个元素附带一个评估值，出队时取出估值最大的一个，等价于一个二叉堆。

（2）双端队列 deque

队列的两端都能插入或取出元素。

2.广度优先搜索 BFS

~~没什么好讲的~~。给个题单

3.单调队列

与单调栈类似，维护队内元素的单调性，及时排除不可能的情况。

单调队列也是优化动态规划的重要手段。

队列的典型例题

1. 蚯蚓

Ac code

#include<bits/stdc++.h>
#define p u/v 
using namespace std;
long long n,m,q,u,v,t,a[100005];
queue <long long> q1,q2,q3;
long long get(){
    long long qa,qb,qc,maxx;
    qa = qb = qc = -2e9;
    if(!q1.empty()) qa = q1.front();
    if(!q2.empty()) qb = q2.front();
    if(!q3.empty()) qc = q3.front();
    maxx = max(qa,max(qb,qc));
    if(!q1.empty() && maxx == q1.front()) q1.pop();
    else if(!q2.empty() && maxx == q2.front()) q2.pop();
    else if(!q3.empty() && maxx == q3.front()) q3.pop();
    return maxx; 
}
inline int read(){
    char c;
    int d=0,e=1;
    c=getchar();
    while(!isdigit(c)){
        if(c == '-') e = -1;
        c = getchar();
    }
    while(isdigit(c)){
        d = (d<<1)+(d<<3)+(c^48);
        c = getchar();
    }
    return d*e;
}
void print(long long int d){
    if(d < 0){
        putchar('-');
        d = -d;
    }
    if(d < 10) putchar(d+48);
    else{
        print(d/10);
        putchar(d%10+48);
    }
}
int main(){
    n = read();
    m = read();
    q = read();
    u = read();
    v = read();
    t = read();
    for(int i = 1;i <= n;i++)
        a[i] = read();
    sort(a+1,a+1+n);
    for(int i = n;i >= 1;i--)
        q1.push(a[i]);
    for(int i = 1;i <= m;i++){
        long long maxx = get()+(i-1)*q;
        if(i % t == 0){
            print(maxx);
            putchar(' ');
        }
        q2.push(maxx * p - q * i);
        q3.push(maxx - maxx * p - q * i);
    }
    putchar('\n');
    for(int i = 1;i <= n+m;i++){
        long long maxx = get()+m*q;
        if(i % t == 0){
            print(maxx);
            putchar(' ');
        }
    }
    return 0;
}

2. 最大子序和

本题是求区间和的问题，我们一般变为前缀和相减来解决。

我们枚举左端点，在规定长度内，找最大的前缀和为右端点。因此，我们用一个队列存这个下标递增，前缀和的值也递增的序列。

每个i都要进行三个步骤，维持长度、更新答案、去除不可能的元素。

Ac code

#include <bits/stdc++.h>
using namespace std;
int n,m,ans = INT_MIN,sum[300005],q[300005],front = 1,back = 1;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i = 1;i <= n;i++){
        int x;
        cin>>x;
        sum[i] = sum[i-1] + x;
    }
    q[1] = 0;
    for(int i = 1;i <= n;i++){
        while(front <= back && i - q[front] > m)
            front++;
        ans = max(ans,sum[i] - sum[q[front]]);
        while(front <= back && sum[q[back]] >= sum[i])
            back--;
        back++;
        q[back] = i;
    }
    cout<<ans;
    return 0;
}

3.Hash表

Hash表的定义

Hash表又称散列表，一般由Hash函数与链表结构（拉链法）或一个大数组（开放选址法） 共同实现。

当需要对较多复杂信息进行统计时，可以用Hash函数把这些信息映射到一个容易维护的域值内。

因为域值变简单，范围变小，可能造成Hash冲突，所以需要上面提到的链表或大数组来解决。

Hash表的用途

1.统计出现次数或是否出现

因为经Hash函数处理的数变简单，范围变小，所以可以更好的完成这类的题目。

2.字符串 Hash

字符串 Hash可以把一个任意长度的字符串映射成一个非负整数，并且冲突的概率极小。具体方法如下：

取一固定值P，把固定值P进制数，并发配一个大于0的数值，代表每种字符。一般来说，我们分配的数值都远小于P。然后取一固定值M,求出该P进制数对M的余数作为该字符串的Hash值。

（通常情况，P取131或13331）

Hash表的典型例题

1. Snowflake Snow Snowflakes

把雪花的六个角按顺时针设为a1,a2,a3,a4,a5,a6,将Hash函数定义为Hash(a1,a2,a3,a4,a5,a6)=(\sum_j^6 + \prod_j^6) mod P (j=1)

如果两片雪花Hash值不同，就说明一定不一样；如果一样，就暴力比较两片雪花是否相同。

#include <bits/stdc++.h>
using namespace std;
const int M = 99991,N = 1e6 + 5;
int n,snow[N][10];
int HEAD[M],NEXT[N],tot;
int Hush(int *a){
    int h=0,j=1;
    for(int i = 0;i < 6;i++){
        h = (h + a[i]) % M;
        j = (long long)j * a[i] % M;
    }
    return (h + j) % M;
}
bool check2(int *a,int *b){
    bool flag;
    for(int i = 0;i < 6;i++){
        for(int j = 0;j < 6;j++){
            flag = true;
            for(int k = 0;k < 6;k++){
                if(a[(i+k) % 6] != b[(j+k) % 6]){
                    flag = false; 
                }
            }
            if(flag) return true;
            flag = true;
            for(int k = 0;k < 6;k++){
                if(a[(i-k+6) % 6] != b[(j+k) % 6]){
                    flag = false; 
                }
            }
            if(flag) return true;
        }
    }
    return false;
}
bool check1(int *a){
    int now = Hush(a);
    for(int i = HEAD[now];i;i = NEXT[i]){
        if(check2(a,snow[i])) return true;
    }
    tot++;
    memcpy(snow[tot],a,6*sizeof(int));
    NEXT[tot] = HEAD[now];
    HEAD[now] = tot;
    return false; 
}
int main(){
    cin>>n;
    while(n--){
        int a[10];
        for(int i = 0;i < 6;i++){
            cin>>a[i];
        }
        if(check1(a)){
            cout<<"Twin snowflakes found.";
            return 0;
        }
    }
    cout<<"No two snowflakes are alike.";
    return 0;
}