AcWing 840. 模拟散列表

模拟散列表 - 哈希表

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 3;

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

void insert(int x){
    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;
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if(*op == 'I') insert(x);
        else{
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

# 在 C++ 中，函数的返回类型如果是 bool 类型，那么函数会在执行到最后一行时自动返回 false。因此，如果将 return false 放在判断语句后面，它会在执行到最后一行之前就被执行，并立即返回 false。

例如，假设函数 find 中包含以下代码：
if (x == 5) return true; return false;
如果 x 等于 5，那么函数会立即返回 true。否则，函数会在执行到最后一行时返回 false。
因此，如果希望函数能够正常执行到最后一行，就应该将 return false 放在判断语句之后。
上面这段代码的意思是，在判断完 x 是否等于 5 之后，再返回 false，从而让函数能够执行到最后一行。

//拉链法

// //1.看一下题目当中的哪儿些操作可以进行优化 操作有什么特点
// //2.寻找一堆数里的最小值 或者最大值的时候用堆来做
// //3.当想维护一个有序链表的时候就要用平衡树就是set来做
// //4.当想维护区间最大值、区间和可能就要用树状数组或者线段树来做
// //5.并查集的题目可能不是很好看出来 不是很直观 所以需要多练题
 #include <iostream>
 #include <cstring>

 using namespace std;

 const int N = 1e5 + 3; //1e5之后的第一个质数是1e5 + 3

 int h[N];

 int e[N], ne[N], idx;
 //单链表的三个：e[N]值, ne[N]下一个位置, idx现在维护的位置

 void insert(int x){
     int k = (x % N + N) % N;//为什么要 + N 再 % N 因为在C++中 负数 % 数 = 负数 正数 % 数 = 正数 因为要保持 % 后的数是正数所以需要 + N % N
    
    
     //单链表插入操作
     e[idx] = x, ne[idx] = h[k], h[k] = idx++;
 }

 bool find(int x){
     int k = (x % N + N) % N;//同样把x映射到从0到N-1之间的一个数
     //在k定义的链表里面找一下存不存在x
     for(int i = h[k]; i != -1; i = ne[i])
         if(e[i] == x)
             return true;
            
     return false;
 }

 int main(){
     int n;
     scanf("%d", &n);
    
    
     memset(h, -1, sizeof h);//所有的槽需要清空 单链表的空指针都用-1来表示
    
     while(n--){
         char op[2];
         int x;
         scanf("%s%d", op, &x);
        
         if(*op == 'I') insert(x);
         //*即根据地址找变量
         else{
             if(find(x)) puts("Yes");
             else puts("No");
         }
     }
    
    
    
     return 0;
 }

// 开放寻址法
#include <cstring>
#include <iostream>

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;//0x3f3f3f3f是一个大于10^9的数

int h[N];

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;
    scanf("%d", &n);
    
    memset(h, 0x3f, sizeof h);
    
    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        
        int k = find(x);
        if(*op == 'I') h[k] = x;
        else{
            if(h[k] != null) puts("Yes");
            else puts("No");
        }
    }
    
    
    return 0;
}