AcWing 840. 模拟散列表
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-16 12:03:38
,
所有人可见
,
阅读 289
#include <iostream>
//首先来找到大于100000的第一个质数是多少
using namespace std;
int main() {
//此时寻找质数的方法是, 如果一个数不是质数, 肯定有一个大于sqrt(n)的约数, 一个小于sqrt(n)的约数
for (int i = 100000;; i ++) {
//开始的时候从100000开始来进行遍历
bool flag = true;
//此时就是来枚举i的每一个质因子
for (int j = 2; j * j <= i; j ++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
cout << i << endl;
break;
}
}
return 0;
}
//======================这是来解决这个问题第一个要来处理的问题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
//如果此时全部都是冲突发生在同一位置上, 此时此位置开始的链表的长度为N
int h[N], e[N], ne[N], idx;
void insert(int x) {
//在c ++中, 对于这个式子 (x % N) 如果x是正数的时候, 此时的余数是正数, 如果是负数, 此时的余数是负数。
//此时在查询的时候, 同样使用这个哈希函数来找到相应的节点的位置
int k = (x % N + N) % N;
//此时插入就是将当前的这个点插入到h[k]位置开始的链表当中
e[idx] = x;
ne[idx] = h[k]; //此时h[k] = -1, 表示的是头结点
h[k] = idx ++;
}
bool query(int x) {
//同样是来使用哈希函数将每一个数映射至数组中的位置
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i]) {
if (x == e[i]) {
return true;
}
}
return false;
}
int main() {
int n;
scanf("%d", &n);
//此时因为是将数组中的每一个位置来作为头结点, 所以此时将数组中是每一个位置上的值全部都设置为-1
memset(h, -1, sizeof(h));
while (n --) {
char op[2];
int x;
//此时使用scanf来读入字符串, 此时使用这种方式读取的时候, 会自动将回车
//空格, 制表符忽略。使用这种方式来读入字符串可以降低输入的时候的问题;
//所以此时使用scanf来读取字符串数组
scanf("%s%d", op, &x);
if (op[0] == 'I') insert(x);
else {
if (query(x)) puts("Yes");
else puts("No");
}
}
return 0;
}