NOJ --138 找球号（二）

     最基础的哈希表用法，先看所要存的个数，一般都是10N+10的内存，这样相当于十个位置里面有一个，空间是足够的。之前一直一直都是超时，就是因为内存开小的话就会出现死循环，因为存不了那么多个数

 

#include<stdio.h> #include <string.h> #include <algorithm> using namespace std; const int base =10000010; int h[base]; void hash(int k) {int m=k%base;if(m<0) m+=base;while(m++,1){if(m>=base) m=m%base;if(h[m]==-1){h[m]=k;break;}if(h[m]==k)break; //当出现一样的数时，只需存一次} } bool find_haxi(int k) {int m=k%base;if(m<0) m+=base;bool flage=false;while(m++,1){if(m>=base) m=m%base;if(h[m]==-1){break;}if(h[m]==k){flage=true;break; //找到了；}}return flage; } int main() {int n, m, ok;char s[1000];scanf("%d", &n);memset(h, -1,sizeof(h));while(n--){scanf("%S%d", s, &m);if(s[0]=='A'){while(m--){scanf("%d",&ok);hash(ok);}continue;}while(m--){scanf("%d", &ok);if(find_haxi(ok)){puts("YES");continue;}puts("NO");}}return 0; }

哈希表的模板

#include<stdio.h> #include<stdlib.h> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int base = 1000000; int h[base+10]; bool flage; void Init() {//hash数组初始化全为-1//如存在-1需特判memset(h,-1,sizeof(h)); } void Hash(int k) {int m = k % base;if(m < 0) m += base;while(m++,1){if(m >= base) m %= base;if(h[m] == -1){h[m] = k;break;}if(h[m] == k)break;} } bool Find_Hash(int k) {int m = k % base;if(m < 0) m += base;bool loop = false;while(m++,1){if(m >= base) m %= base;if(h[m] == -1)break;if(h[m] == k){loop = true;break;}}return loop; }

 还有一种就是不需要开那么大内存，就是用vector来写，因为是数组所以不需要开那么大的内存。直接在找的那组余数里面找看是否有存在这个数。

#include <vector> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; const int base =10000; vector<int> m[base]; void find(int x) {int b=x%base;m[b].push_back(x); } void hash(int x) {int c,flage=0;int b=x%base;c=m[b].size();for(int i =0 ;i<c; i++){if(m[b][i]==x){puts("YES");flage=1;break;}}if(!flage)puts("NO"); } int main() {int n,m;scanf("%d", &n);while(n--){char s[100];int m, i;scanf("%s%d", s, &m);if(s[0]=='A')while(m--){scanf("%d", &i);find(i);}elsewhile(m--){scanf("%d",&i);hash(i);}}return 0; }

 

总结

以上是生活随笔为你收集整理的NOJ --138 找球号（二）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。