100000582 - 《算法笔记》4.2小节——算法初步->哈希

《算法笔记》4.2小节——算法初步->哈希

1、直接把输入的数（<10^5）作为数组的下表，来对这个书的性质进行统计（用空间换时间），复杂度由O(n)减到O(1)
例1：统计M个数是否出现在N个数中

#include <stdio.h>
const int maxn = 100010;
bool hashTable[maxn] = { false };

int main() {
	int n, m, x;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		hashTable[x] = true;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d", &x);
		if (hashTable[x] == true) printf("YES\n");
		else printf("FALSE\n");
	}
	return 0;
}

例2：统计M个数在N个数中出现的次数

#include <stdio.h>
const int maxn = 100010;
int hashTable[maxn] = { 0 };

int main() {
	int n, m, x;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		hashTable[x]++;;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d", &x);
		printf("%d", hashTable[x]);
	}
	return 0;
}

2、使用map函数 （C++11后用unordered_map，速度更快），除非对效率要求高

3、字符串hash、
3.1、二维整点坐标映射
P(x,y)(0<=x,y<=range)，hash函数可为H§=x*range+y
3.2、字符串映射
字符串：大写字母，可视为（26进制转换为10进制）；小写字母，可是为（52进制转换为10进制）

int hashFunc(char s[], int len) {
	int id = 0;
	for (int i = 0; i < len; i++) {
		if (s[i] >= 'A'&&s[i] <= 'Z') id = id * 26 + (s[i] - 'A');
		else if (s[i] >= 'a'&&s[i] <= 'z') id = id * 52 + (s[i] - 'a') + 26;
	}
	return id;
}

字符串+数字：可按照扩大至62进制转换；若末尾是确定个数的数字，则可将前面的字母转换后，直接拼接上末尾的数字，如BCD8，可在末尾加

id = id * 10 + (s[len - 1] - '0');

1782 Problem A 谁是你的潜在朋友

#include <cstdio>
#include <cstring>

int main() {
	int n, m;
	while (scanf("%d %d", &n, &m) != EOF) {
		int book[210] = { 0 };
		int p[210] = { 0 };
		for (int i = 0; i < n; i++) {
			scanf("%d", &p[i]);
			if(p[i]<=m&&p[i]>0) book[p[i]]++;
		}
		for (int i = 0; i < n; i++) {
			if (book[p[i]] == 0 || book[p[i]] == 1) printf("BeiJu\n");
			else printf("%d\n", book[p[i]] - 1);
		}
	}
	return 0;
}

2066 Problem B 分组统计
输出有点绕，注意条件

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
	int m;
	while (scanf("%d", &m)!=EOF) {
		while (m--) {
			int n;
			scanf("%d", &n);
			int num[110];
			int team[110];
			int a[110][2110] = { 0 };
			for (int i = 0; i < n; i++) {
				scanf("%d", &num[i]);
			}
			for (int i = 0; i < n; i++) {
				scanf("%d", &team[i]);
				a[team[i]][num[i]]++;
			}
			sort(num, num + n);
			sort(team, team + n);
			int teamtemp = team[0];
			for (int i = 0; i < n; i++) {
				if (i == 0 || (i > 0 && team[i] != teamtemp)) {
					printf("%d={", team[i]);
					int numtemp = num[0];
					for (int j = 0; j < n; j++) {

						if (j == 0 || (j > 0 && num[j] != numtemp)) {
							printf("%d=%d", num[j], a[team[i]][num[j]]);
							if (j != n - 1 && num[j] != num[n - 1]) printf(",");
						}
						if (numtemp != num[j]) numtemp = num[j];
					}
					printf("}\n");
					if (teamtemp != team[i]) teamtemp = team[i];
				}
			}
		}
	}
	return 0;
}

6112 Problem C/1041 Be Unique (20分)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 10010

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		int lottery[100010], lottery_cnt[maxn] = { 0 };
		for (int i = 0; i < n; i++) {
			scanf("%d", &lottery[i]);
			lottery_cnt[lottery[i]]++;
		}
		int i = 0;
		for (; i < n; i++) {
			if (lottery_cnt[lottery[i]] == 1) {
				printf("%d\n", lottery[i]);
				break;
			}
		}
		//或者前面加flag判断
		if (i == n && lottery_cnt[lottery[i]] != 1) printf("None\n");
	}

	return 0;
}

6120 Problem D String Subtraction (20)

#include <stdio.h>
#include <string.h>
int main() {
	char s1[10010], s2[10010];
	while (gets(s1) && gets(s2)) {
		for (int i = 0; i < strlen(s1); i++) {
			int flag = 0;
			for (int j = 0; j < strlen(s2); j++) {
				if (s1[i] == s2[j]) {
					flag = 1;
					break;
				}
			}
			if (flag == 0) printf("%c", s1[i]);
		}
	}
	return 0;
}

改进，用flag数组标记某字符是否在s2中出现

#include <stdio.h>
#include <string.h>

int main() {
	char s1[10010], s2[10010];
	while (gets(s1) && gets(s2)) {
		int flag[255] = { 0 };
		//或用s2[i]!='\0'
		for (int i = 0; i < strlen(s2); i++) {
			flag[s2[i]] = 1;
		}
		for (int i = 0; i < strlen(s1); i++) {
			if (flag[s1[i]] == 0) printf("%c", s1[i]);
		}
	}
	return 0;
}