目錄

散列

字符出現次數

?力扣經典題：兩數之和

?集合運算

交

并?

差?

?字符串的出現次數

---

散列

導入：

有N個數和M個數，如何判斷M個數中每個數是否在N中出現？

思想：空間換時間

創建hashtable，以N個數本身為索引（數組下標）構建 bool hashtable

輸入x的過程中，hashtable[x]=True（若要計算出現次數，換成++）

但終歸是有局限性！數字只能是整數，還不能太大，等等。

散列函數：平房區中法、取余數……

可能會沖突：（即：不是單射了）

?字符串哈希：借鑒26進制的推廣：62進制

字符是否出現

?如何判斷輸完了？

本地devc++我可以說：c1!='\n',c1!=' ','a'<=c1<='z'都能跑，如

#include<stdio.h>
#include<string>
using namespace std;
int main()
{printf("%d",'\n'>='a');
//    char c1[27];
char c1;char c2[27]={0};
int i=0;
scanf("%c",&c1);
while(c1>='a'&&c1<='z')
{c2[c1-'a']++;scanf("%c",&c1);
}
for(int j=0;j<26;j++)
if(c2[j]>0) printf("%c %d\n",'a'+j,c2[j]);
}

然而網站上不行，得用while(scanf("%c",&c1)!=EOF)
?

#include<stdio.h>
#include<string>
using namespace std;
int main()
{
//    char c1[27];
char c1;char c2[27]={0};
int i=0;
// scanf("%c",&c1);
while(scanf("%c",&c1)!=EOF)
{c2[c1-'a']++;// scanf("%c",&c1);
}
for(int j=0;j<26;j++)
if(c2[j]>0) printf("%c %d\n",'a'+j,c2[j]);
}

?這個本地不能跑了。。

行吧，得改頭換面用cstring

字符出現次數

?這里我忘了這個：

就算你定義char a[1000]，如果賦值“avx”，仍然可以使用長度strlen，仍為3

我的代碼

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{char s1[1001],s2[1001];int s[26]={0};scanf("%s",&s1);scanf("%s",&s2);for(int i=0;s1[i]>='a'&&s1[i]<='z'&&i<1001;i++)s[s1[i]-'a']=1;for(int i=0;s2[i]>='a'&&s2[i]<='z'&&i<1001;i++)
{if(i==0)		printf("%d",s[s2[i]-'a']);else	printf(" %d",s[s2[i]-'a']);
}}

?答案

#include <cstdio>
#include <cstring>const int MAXN = 26;
const int MAXL = 1001;
char str1[MAXL], str2[MAXL];
bool hashTable[MAXN] = {false};int getHashKey(char c) {return c - 'a';
}int main () {scanf("%s%s", str1, str2);int len1 = strlen(str1);int len2 = strlen(str2);for (int i = 0; i < len1; i++) {hashTable[getHashKey(str1[i])] = true;}for (int i = 0; i < len2; i++) {printf("%d", hashTable[getHashKey(str2[i])]);printf(i < len2 - 1 ? " " : "\n");}return 0;
}

?力扣經典題：兩數之和

簡單版

?我的代碼（devc++int數組長度設為1000000報錯，但是網上通過了）

 #include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int A[n];
int h[1000000]={0};
int ans=0;
int a0=0;
for(int i=0;i<n;i++)
{scanf("%d",&a0);A[i]=a0;h[A[i]]++;	 
}for(int i=0;i<n;i++)
{
if(k>=A[i])
{
if(A[i]<=k-A[i])
{if(A[i]==k-A[i]){if(h[A[i]]>1)ans++;//printf("-%d-",A[i]);	}else if(h[k-A[i]]>0) ans++;//printf("-%d-",A[i]);
}
else break;
}
}
printf("%d",ans);}

答案（他是遍歷整個，再除以二）?

#include <cstdio>const int MAXN = 100000;
const int MAXK = 1000001;
int a[MAXN], hashTable[MAXK] = {false};int main () {int n, k;scanf("%d%d", &n, &k);for (int i = 0; i < n; i++) {scanf("%d", &a[i]);hashTable[a[i]] = true;}int ans = 0;for (int i = 0; i < n; i++) {if (k - a[i] >= 0 && hashTable[k - a[i]]) {ans++;}}printf("%d", ans / 2);return 0;
}

?集合運算

交

思路：第一個數組構造哈希表，然后遍歷第二個，輸出值為1者

數組長度10001錯誤，數組長度20000，通過。。

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20010],h2[20010];
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;//求交集：if(h1[a0]) {if(flag) printf(" %d",a0);else printf("%d",a0);flag=1;} 
//	h2[B[i]]++;	 
}}

并?

?思路：遍歷第一個數組構造哈希表，然后遍歷第二個，把第一個為0的但第二個出現的數字的哈希值改為1，最后遍歷整個表，輸出值為1的

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20000]={0},h2[20000]={0};
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;//求交集：
//	if(h1[a0]) 
//	{
//		if(flag) printf(" %d",a0);
//		else printf("%d",a0);
//		flag=1;
//	} 
//并集if(!h1[a0]) h1[a0]++;
}
//并集：整個兒遍歷10000？for(int i=0;i<20000;i++)
if (h1[i])
{if(flag) printf(" %d",i);else printf("%d",i);flag=1;}		}

差?

?思路：遍歷第一個造出哈希表，遍歷第二個，每找一個，哈希表對應值-1；最后遍歷第一個集合，每輸出一次，哈希值-1，直至為0

#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
int n1,n2;
scanf("%d %d",&n1,&n2);
int A[n1],B[n2],h1[20000]={0},h2[20000]={0};
int a0=0;
for(int i=0;i<n1;i++)
{scanf("%d",&a0);A[i]=a0;h1[A[i]]++;	 
}
bool flag=0;
for(int i=0;i<n2;i++)
{scanf("%d",&a0);B[i]=a0;
//求差集 if(h1[a0]) h1[a0]--;
}
for(int i=0;i<n1;i++)	
{while(h1[A[i]]){if(flag) printf(" %d",A[i]);else printf("%d",A[i]);flag=1;h1[A[i]]--;}} 
}//求交集：
//	if(h1[a0]) 
//	{
//		if(flag) printf(" %d",a0);
//		else printf("%d",a0);
//		flag=1;
//	} 
//并集
// 	if(!h1[a0]) h1[a0]++;
//}
//并集：整個兒遍歷10000？
//for(int i=0;i<20000;i++)
//if (h1[i])
//{if(flag) printf(" %d",i);
//		else printf("%d",i);
//		flag=1;
//		}		

?字符串的出現次數

我：

#include<stdio.h>
#include<cstring>
using namespace std;
int abc(char str[4])
{return (str[0]-'A')*26*26+(str[1]-'A')*26+(str[2]-'A');
}int main()
{int n1,n2;scanf("%d",&n1);
char s1[n1+1][5];
int si1[20000]={0};
for(int i=0;i<n1;i++)
{scanf("%s",s1[i]);
//	printf("%d",abc(s1[i]));si1[abc(s1[i])]++;
//	printf("%s&%d",s1[i],si1[abc(s1[i])]);}
scanf("%d",&n2);
char s2[n2+1][5];
for(int i=0;i<n2;i++)
{scanf("%s",s2[i]);if (si1[abc(s2[i])]) printf("%d",si1[abc(s2[i])]);else printf("0");if (i<n2-1) printf(" ");}//COD
//ABA}

?答案

#include <cstdio>const int MAXN = 26 * 26 * 26;
const int MAXL = 1001;
char str[MAXL];
int hashTable[MAXN] = {0};int getHashKey(char s[]) {return (s[0] - 'A') * 26 * 26 + (s[1] - 'A') * 26 + (s[2] - 'A');
}int main () {int n, m;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", str);hashTable[getHashKey(str)]++;}scanf("%d", &m);for (int i = 0; i < m; i++) {scanf("%s", str);printf("%d", hashTable[getHashKey(str)]);printf(i < m - 1 ? " " : "\n");}return 0;}