???? 最基礎(chǔ)的哈希表用法，先看所要存的個數(shù)，一般都是10N+10的內(nèi)存，這樣相當(dāng)于十個位置里面有一個，空間是足夠的。之前一直一直都是超時，就是因?yàn)閮?nèi)存開小的話就會出現(xiàn)死循環(huán)，因?yàn)榇娌涣四敲炊鄠€數(shù)

?

#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; //當(dāng)出現(xiàn)一樣的數(shù)時，只需存一次} } 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數(shù)組初始化全為-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; }

?還有一種就是不需要開那么大內(nèi)存，就是用vector來寫，因?yàn)槭菙?shù)組所以不需要開那么大的內(nèi)存。直接在找的那組余數(shù)里面找看是否有存在這個數(shù)。

#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; }

?

總結(jié)

以上是生活随笔為你收集整理的NOJ --138 找球号（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。