AcWing 840. 模拟散列表-java 拉链法,用数组模拟链表
原题链接
简单
作者:
韦德
,
2021-06-13 17:59:18
,
所有人可见
,
阅读 379
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 100010;
// 哈希数组的长度
static int Z = 10003;
static int index = 0;
static int[] h;
static int[] l;
static int[] ne;
static void init(){
h = new int[Z];
l = new int[N];
ne = new int[N];
// 将每个头节点初始化为-1
for (int i = 0;i<h.length;i++){
h[i] = -1;
}
}
static void insert(int num){
int i = (num % Z + Z) % Z;
l[index] = num;
ne[index] = h[i];
// 在哈希表的链表上村的是单链表的下标
h[i] = index;
index++;
}
static boolean query(int num){
int i = (num % Z + Z) % Z;
for (int cur = h[i];cur != -1;cur = ne[cur]){
if(l[cur] == num){
return true;
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
init();
while (n > 0){
n--;
String[] cur = reader.readLine().split(" ");
if(cur[0].equals("I")){
insert(Integer.parseInt(cur[1]));
}else{
System.out.println(query(Integer.parseInt(cur[1])) ? "Yes" : "No");
}
}
}
}