《算法笔记》4.2小节——算法初步->哈希
2020-04-08 本文已影响0人
木子李_0961
@[TOC]
Contest100000582 - 《算法笔记》4.2小节——算法初步->哈希
讲解：
4.2.1 散列的定义与整数散列
解决冲突的方法：
开放定址法：1）线性探查法 2）平方探查法 3）链地址法
HashTable1
#include <cstdio>
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;//数字x出现过
}
for(int i=0;i<m;i++)
{
scanf("%d",&x);
if(hashTable[x] == true)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
HashTable2
//HashTable2
#include <cstdio>
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]++;//数字x出现次数统计
}
for(int i=0;i<m;i++)
{
scanf("%d",&x);
printf("%d\n",hashTable[x]);//输出次数
}
return 0;
}
4.2.2 字符串hash初步
//字符串hash初步
int hashFunc(char S[],int len)//hash函数，将字符串S转换为整数
{
int id=0;
for(int i=0;i<len;i++)
{
if(S[i] >= 'A'&&S[i] <= 'Z')
id = id*52 + (S[i]-'A');//将26进制转换为10进制
else if(S[i]>='a'&&S[i] <= 'z')
id = id*52 + (S[i]-'a')+26;//+26社么鬼
}
return id;
}
例题：
给出N个字符串（恰好三位大写字母组成），再给出M个查询字符串，问每个查询字符串 在N个字符中出现的次数
题析：注意此处前面学习知识的应用
#include <iostream>
const int maxn = 100;
char S[maxn][5],temp[5];
int hashTable[26*26*26+10];
int hashFunc(char S[],int len)//hash函数，将字符串s转换为整数
{
int id = 0;
for(int i=0;i<len;i++)
{
id = id*26+(S[i]-'A');
}
return id;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s",S[i]);
int id = hashFunc(S[i],3);//将字符串S[i]转换为整数
hashTable[id]++;//该字符串出现次数加1
}
for(int i=0;i<m;i++)
{
scanf("%s",temp);
int id = hashFunc(temp,3);//将字符串temp转换为整数
printf("%d\n",hashTable[id]);//输出该字符串的出现次数
}
return 0;
}
练习:
1782 Problem A 谁是你的潜在朋友
来自 http://codeup.cn/contest.php?cid=100000582
题析：
这题貌似不难，但是也搞得我改几次，主要是数组下标和题目的理解（朋友不包括自己）
总结还是自己太菜了
//1782ProblemA谁是你的潜在朋友
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF)
{
// int like[205]={0};//存储读者喜欢的图书编号
// int cnt[205]={0};//记录喜欢编号出现的次数 //直接赋值0初始化
int like[205];
int cnt[205];
memset(cnt,0,sizeof(cnt));//函数初始化
// for(int i=1;i<=n;i++)//关于下标的问题
for(int i=0;i<n;i++)
{
scanf("%d",&like[i]);
cnt[like[i]]++;
// cout<<like[i]<<endl;//测试输出中间结果
// cout<<cnt[like[i]]<<endl;
}
for(int i=0;i<n;i++)
//第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的
//图书的编号,所以必须使i从0开始
{
if(cnt[like[i]] == 1)//计数为1表示只有自己
printf("BeiJu\n");
else
printf("%d\n",cnt[like[i]]-1);//输出相同人数，需要减去自己
}
//思考：若此处用M: for(int i=0;i<m;i++)
//自问自答：不行！//因为需要按照输入顺序输出，所以不可以直接用cnt计数矩阵处理
}
return 0;
}
2066 Problem B 分组统计
来自 http://codeup.cn/contest.php?cid=100000582
题析：
经典题目，较繁琐，值得咀嚼
膜大佬，主流三款，这个思路最清晰
https://blog.csdn.net/xunalove/article/details/87904303
#include <iostream>
#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);
//输入第一行数，存入arr1[]中，同时使用hashTable1[]函数去重，将去重后的数存入num[]中，并排序。
int hashTable1[100005]={0};
int arr1[105],num[105],cnt1=0,maxn=0;
for(int i=0;i<n;i++)
{
scanf("%d",&arr1[i]);//读入数据
if(hashTable1[arr1[i]]==0)//去重
{
hashTable1[arr1[i]]++;//未重复则加一
num[cnt1++] = arr1[i];//读入数
}
//1. 用ans[ i ][ j ],i存放的是第二行的组号，组号肯定是小于n(n<100) , 而 j 存放的是第一行的数，
//这个数题目是没有给范围的，如果二维数组开的太小，很容易溢出，出现50%错误的，
//所以再输入第一行数据是记录出最大的值，将其+10作为二维数组中的 j 即可解决。
if(maxn<arr1[i])//记录arr1数组大小
maxn = arr1[i];
}
sort(num,num+cnt1);//排序
//输入第二行数，存入arr2[]中，同时使用hashTable2[]函数去重，将去重后的数存入cg[]中，并排序。
int hashTable2[100005]={0};
int arr2[105],cg[105],cnt2=0;
int ans[n+5][maxn+5]={0};//注意数组范围，没有限定arr1[i]的取值，容易50%错误
for(int i=0;i<n;i++)
{
scanf("%d",&arr2[i]);
//将arr2[]和arr1[]对应存入ans[][]中，ans[i][j] i为分组，j为数 a[i][j]为第i组的j数出现的次数。
ans[arr2[i]][arr1[i]]++;//arr2[i]组中arr1[i]数出现的次数，//注意数组范围，没有限定arr1[i]的取值，容易50%错误
if(hashTable2[arr2[i]] == 0)//去重
{
hashTable2[arr2[i]]++;
cg[cnt2++] = arr2[i];//去重后分组存入cg
}
}
sort(cg,cg+cnt2);//排序
//遍历输出
for(int i=0;i<cnt2;i++)
{
printf("%d={",cg[i]);
for(int j=0;j<cnt1;j++)
{
printf("%d=%d",num[j],ans[cg[i]][num[j]]);
if(j<cnt1-1)
printf(",");
else
printf("}\n");
}
}
}
}
return 0;
}
6112 Problem C Be Unique (20)
来自 http://codeup.cn/contest.php?cid=100000582
题析：
较简单
//6112ProblemC Be Unique (20)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int num[10010]={0};
int bet[100010]={0};//注意范围
int n;int i;
while(scanf("%d",&n) != EOF)
{
// int i;
for(i=0;i<n;i++)
{
scanf("%d",&num[i]);//输入n个数
bet[num[i]]++;//对应的猜数哈希表项值加一，记录该数出现的次数
}
// int flag=0;
for(i=0;i<n;i++)
{
if(bet[num[i]]==1)
{
printf("%d\n",num[i]);
// flag=1;
// return 0;//跳出循环的处理方法多样
break;
}
}
// if(flag==0)
if(i==n)
printf("None\n");
}
return 0;
}
6120 Problem D String Subtraction (20)
来自 http://codeup.cn/contest.php?cid=100000582
题析：
思路比较简单的题，竟出了许多幺蛾子，详情见注释
bool与int;0、1与false/true
Scanf()与gets()
!=1与==0关系？？
if(visit[str[i]-'A'] != 1)与if(visit[int(str[i])] != 1)效果一致，字符与数字之间的转换
//6120ProblemD String Subtraction (20)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
char str[10005];
char substr[10005];
// int visit[10005]={false};//int全对，bool错误60% ，0与false等价？？int数组可以赋值false??
int visit[10005]={0};
while(gets(str) != NULL)//多点测试、单点测试都可以
{
// gets(str);
int len=strlen(str);
// scanf("%s",substr);//错误20%，子字符串可能有空格
gets(substr);
int sublen=strlen(substr);
for(int i=0;i<sublen;i++)
{
// visit[substr[i]-'A']=true;
visit[substr[i]-'A']=1;
}
for(int i=0;i<len;i++)
{
// if(visit[str[i]-'A'] != true)//正确
if(visit[str[i]-'A'] != 1)//正确
// if(visit[str[i]-'A'] == 0)//错误60%
printf("%c",str[i]);
}
printf("\n");
}
return 0;
}
