二、数据结构-哈希表

模拟散列表

https://www.acwing.com/problem/content/842/

//拉链法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 3; //大于1e5的第一个质数
int h[N], e[N], ne[N], idx;
int n;

void insert(int x){
    //加N防止模出来的数是负数
    int k = (x % N + N) % N; 
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx;
    idx++;
}

int find(int x){
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]){
        if(e[i] == x){
            return 1;
        }
    }
    return 0;
}
 
int main(){
    cin>>n;
    memset(h, -1, sizeof(h));
    char c;
    while(n--){
        cin>>c;
        int x;
        if(c == 'I'){
            cin>>x;
            insert(x);
        }else{
            cin>>x;
            if(find(x)){
                cout<<"Yes"<<endl;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}

//开放寻地址法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 3, null = 0x3f3f3f3f; //第一个大于2e5的质数
int h[N];
int n;

int find(int x){
    int k = (x % N + N) % N;
    //如果k位置不等于x，那就找下一个数
    while(h[k] != x && h[k] != null){
        k++;
        //到结尾也没找到，就从头开始找
        if(k == N){
            k = 0;
        }
    }
    return k;
}

int main(){
    memset(h, 0x3f, sizeof(h));
    cin>>n;
    char c;
    while(n--){
        cin>>c;
        int x;
        if(c == 'I'){
            cin>>x;
            //找到第一个空位置
            int k = find(x);
            h[k] = x;
        }else{
            cin>>x;
            //查询是否有x存在
            int k = find(x);
            cout<<(h[k] == x ? "Yes" : "No")<<endl;
        }
    }
    return 0;
}

字符串哈希

https://www.acwing.com/problem/content/843/

#include<iostream>
using namespace std;
const int N = 1e5 + 10, p = 131; //p为131或13331，2的64次方，溢出int就等效于取模了
unsigned long long a[N], b[N]; //a存储前缀和，b存储要乘的进位数
char s[N];
int n, m;

//初始化
void init(){
    b[0] = 1;
    for(int i = 1; i <= n; i++){
        a[i] = a[i - 1] * p + s[i];
        b[i] = b[i - 1] * p;
    }
}

unsigned long long get(int l, int r){
    return a[r] - a[l - 1] * b[r - l + 1];
}

int main(){
    cin>>n>>m>>s + 1;
    init();
    int l1, r1, l2, r2;
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        cout<<(get(l1, r1) == get(l2, r2) ? "Yes" : "No")<<endl;
    }
    return 0;
}