算法竞赛--散列

散列:

将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。

1.字符串统计

给出N个字符串(由恰好三个大写字母组成),再给出M个查询字符串，问每个查询字符串在N个字符串中出现的次数.

思路:用字符串通过散列转换为数字作为下标进行计数，数组中记录每个字符串出现的次数，再将查询字符串转换为数字，匹配下标，输出数组中所记录的个数.

代码如下:

#include<stdio.h>
int h[4000];
int hash(char a[],int len)	//将字符串进行转换
{
	int sum=0;
	for(int i=0;i<len;i++)
		sum=sum*26+a[i]-'A';
	return sum;
}
int main()
{
	int N,M;
	char a[10],b[10];
	scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++)		//将N个字符串分别转换为数字，数字所对应的下标记录出现的次数。
	{
		scanf("%s",a);
		h[hash(a,3)]++;
	}
	for(int i=0;i<M;i++)		//输入查询字符串，转换为数字，将数字所对应的下标的数组输出。
	{
		scanf("%s",b);
		printf("%d\n",h[hash(b,3)]);
	}
	return 0;
}

2.String Subtraction

Given two strings S1 and S2, S = S1 - S2 is defined to be the remaining string after taking all the characters in S2 from S1. Your task is simply to calculate S1 - S2for any given strings. However, it might not be that simple to do it fast.

输入信息:

Each input file contains one test case. Each case consists of two lines which gives S1 and S2, respectively. The string lengths of both strings are no more than 104. It is guaranteed that all the characters are visible ASCII codes and white space, and a new line character signals the end of a string.

输出信息:

For each test case, print S1 - S2 in one line.

样例输入:

1 2	They are students. aeiou

样例输出:

1	Thy r stdnts.

思路:运用哈希函数，将s2中出现的字符标志设置为true，在s1中遍历，将为false的字符输出。

注意:

1.多层循环嵌套会导致运行超时

2.注意字符串的范围，会导致RE60%

代码如下:

#include <stdio.h>
#include <string.h>
bool H[26];
int main()
{
	char a[10100],b[10100];
	gets(a);
	gets(b);
	int la=strlen(a);
	int lb=strlen(b);
	for(int i=0;i<lb;i++)		//在字符串b中出现，设置标志位为true.
		H[b[i]]=true;
	for(int i=0;i<la;i++)
		if(H[a[i]]==false)		//标志位为false，输出该字符
			printf("%c",a[i]);
	printf("\n");
	return 0;
}

3.Be Unique

Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1,10000 ]. The first one who bets on a unique number wins. For example, if there are 7 people betting on { 5 31 5 88 67 88 17 }, then the second one who bets on 31 wins.

输入信息:

Each input file contains one test case. Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets. The numbers are separated by a space.

输出信息:

For each test case, print the winning number in a line. If there is no winner, print “None” instead.

样例输入:

1 2	7 5 31 5 88 67 88 17 5 888 666 666 888 888

样例输出:

1
2

31
None

代码如下:

#include <stdio.h>
int main()
{
	int N,count=0;
	while(scanf("%d",&N)==1)
	{
		int a[10010]={0};
		int b[10010]={0};
		for(int i=0;i<N;i++)
		{
			int m;
			scanf("%d",&m);		\\输入m，并记录次数
			a[m]++;
			if(a[m]==1)	\\如果是第一次，该数字第一次出现，将该数字存储在b中
			b[count++]=m;
		}
		int j;
		for(j=0;j<count;j++)
			if(a[b[j]]==1)
			{
				printf("%d\n",b[j]);
				break;
			}
		if(j==count)
			printf("None\n");
	}
	return 0;
}

4.分组统计

先输入一组数，然后输入其分组，按照分组统计出现次数并输出，参见样例。

输入信息:

输入第一行表示样例数m，对于每个样例，第一行为数的个数n，接下来两行分别有n个数，第一行有n个数，第二行的n个数分别对应上一行每个数的分组，n不超过100。

输出信息:

输出m行，格式参见样例，按从小到大排。

样例输入:

1
7
3 2 3 8 8 2 3
1 2 3 2 1 3 1

样例输出:

1
2
3

1={2=0,3=2,8=1}
2={2=1,3=0,8=1}
3={2=1,3=1,8=0}

注意:哈希数组要选的大一些，否则会WA50%。

代码如下:

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
	int n,m;
	while(scanf("%d",&m)==1)	//输入样例数m
	{
		for(int i=0;i<m;i++)
		{
			int s[100]={0},g[100]={0};
			int a[100][2100]={{0,0}};	//哈希数组存储出现次数
			scanf("%d",&n);
			for(int j=0;j<n;j++)		//存储一组数
				scanf("%d",&s[j]);
			for(int j=0;j<n;j++)
			{
				scanf("%d",&g[j]);		//存储每个数对应组
				a[g[j]][s[j]]++;		//哈希数组存储值
			}
			sort(s,s+n);			//对两个数组从小到大进行排序
			sort(g,g+n);
			for(int j=0;j<n;j++)
			{
				if(g[j]!=g[j-1])	//排序之后，两个不一样才进行输出。
				{
					printf("%d={",g[j]);
					for(int k=0;k<n;k++)
					{
						if(s[k]!=s[k-1])//排序之后，两个不一样才进行输出。
						{
							printf("%d=%d",s[k],a[g[j]][s[k]]);
							if(k!=n-1&&s[k]!=s[n-1])//不是最后一个输出','
								printf(",");	
						}
					}	
					printf("}\n");
				}
			}		
		}
	}
	return 0;
}