当前位置:网站首页>哈希表 AcWing 840. 模拟散列表
哈希表 AcWing 840. 模拟散列表
2022-07-02 09:43:00 【T_Y_F666】
哈希表 AcWing 840. 模拟散列表
原题链接
算法标签
哈希表
思路
拉链法
开放寻址法
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100003;
int a[N], e[N], h[N], ne[N], idx;
int s;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
// 采用头插法 将数据插入对应hash值为k的hash表中
void insert(int x){
//保证负数也可以映射到hash表中 所模数字为质数 可以尽量减少冲突
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;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(h, -1, sizeof h);
int n=read();
while(n--){
char op[2];
scanf("%s", op);
int x=read();
if(op[0]=='I'){
insert(x);
}else{
if(find(x)){
puts("Yes");
}else{
puts("No");
}
}
}
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- (C language) octal conversion decimal
- CPU指令集介绍
- 单指令多数据SIMD的SSE/AVX指令集和API
- CDH6之Sqoop添加数据库驱动
- drools执行指定的规则
- CV2 in OpenCV VideoWriter_ Fourcc() function and cv2 Combined use of videowriter() function
- How to write a pleasing English mathematical paper
- Find the factorial of a positive integer within 16, that is, the class of n (0= < n < =16). Enter 1111 to exit.
- Lekao.com: experience sharing of junior economists and previous candidates in customs clearance
- drools执行String规则或执行某个规则文件
猜你喜欢
(C language) input a line of characters and count the number of English letters, spaces, numbers and other characters.
Docker-compose配置Mysql,Redis,MongoDB
PR 2021 quick start tutorial, learn about the and functions of the timeline panel
Lekao: 22 year first-class fire engineer "technical practice" knowledge points
1380. Lucky numbers in the matrix [two-dimensional array, matrix]
Simple use of drools decision table
堆(優先級隊列)
Interview with meituan, a 34 year old programmer, was rejected: only those under the age of 30 who work hard and earn little overtime
刷题---二叉树--2
Jenkins user rights management
随机推荐
Anxiety of a 211 programmer: working for 3 years with a monthly salary of less than 30000, worried about being replaced by fresh students
Gaode map test case
drools决策表的简单使用
寻找二叉树中任意两个数的公共祖先
Leetcode14 longest public prefix
计数类DP AcWing 900. 整数划分
Intel internal instructions - AVX and avx2 learning notes
Mysql database foundation
Simple use of drools decision table
BOM DOM
Simple understanding of ThreadLocal
Leetcode209 subarray with the smallest length
The differences and relationships among port, targetport, nodeport and containerport in kubenetes
2.6 using recursion and stack - [tower of Hanoi problem]
Leetcode122 the best time to buy and sell stocks II
Lombok common annotations
计算二叉树的最大路径和
包管理工具
Performance tuning project case
arcgis js 4.x 地图中加入图片