AcWing 840. 模拟散列表_Java实现含简要注释
原题链接
简单
作者:
FayunYm
,
2020-12-29 21:24:18
,
所有人可见
,
阅读 380
import java.io.*;
import java.util.Arrays;
public class Main {
static final int N = 100_003;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx;
public static void main(String[] args) throws IOException {
// 找>100_000的质数
// for(int i = 100000;;i++) {
// boolean flag = true;
// for(int j = 2; j * j <= i; j++) {
// if(i % j ==0) {
// flag = false;
// break;
// }
// }
// if(flag) {
// System.out.println(i);
// break;
// }
// }
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine()); //int n = read.read(); reader.readLine();不行,去查一下用法
Arrays.fill(h,-1); //这个可以批量赋值
while(n-- != 0) {
String[] op = reader.readLine().split(" ");
if(op[0].equals("I")) {
insert(Integer.parseInt(op[1]));
} else {
if(find(Integer.parseInt(op[1]))) log.write("Yes\n");
else log.write("No\n");
}
}
// log.write((-10)%3 + "");
log.flush();
log.close();
reader.close();
}
static void insert(int x) {
int k = (x % N + N) % N; //使得结果一定为正
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++; //这两句就是头插
}
static boolean 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;
}
}