hash题型：
1.一般用于查询类的题目
2.统计个数的题目
1.hash最简单的例子是查询数字，记录数字出现的个数。
算法笔记中对散列定义浓缩为一句话：“将元素通过一个函数转换为一个整数，这个整数唯一的代表这个元素”。，那么在查询中直接进行查询就比较方便。
2.关于散列函数：
（1）直接对应法
（2）线性变换（很少用），在(x,y)坐标对应于一个数的时候可以用到
key=x*range+y;
（3）除留余数法：key=key%mod；
可以覆盖0-mod这个范围的数，一般为了尽可能的覆盖范围里面的每一个数，会选择素数。
3.解决冲突的方法
（1）线性扫描法：从当前位置向前扫描，若遇到第一个空位返回即可，若是回到原位证明没有空位。
int LinearP(vector<int>&a,int pos,int n)//a是散列数组，pos是应该在的位置,n是表长
{
int k=1;
if(a[pos]==-1) return pos;//-1说明这个位置是空的
int pos_n=(pos+k)%n;
while((pos_n!=pos)
{
if(a[pos_n]==-1) return pos_n;
k++;
pos_n=(pos+k)%n;
}
return -1;//代表没有找到
}
2（平方探查法）：假设当前位置为key，对key+1^ 2 key-1^ 2 key+2^ 2 key-2^2依次进行探测，如果是整数超过表长，取模即可
负数的话：（取模+size）%size取模
int QuadraticP(vector<int>&a,int pos,int n)
{
int k=1;
if(pos==-1) return pos;
int pos_n=(pos+k)%n;
while(pos_n!=pos)
{
if(a[pos_n]==-1)return pos_n;
k=k*k;//探索正方向
pos_n=(pos+k)%n;
}
k=1;
pos_n=((pos-k)%n+n)%n;
while(pos_n!=pos)
{
if(a[pos_n]==-1)return pos_n;
k=k*k;//探索负方向
pos_n=((pos-k)%n+n)%n;
}
return -1;//没找到
//两个计算可以放到一起，先检测正方向的，然后检测反方向的，结束条件不变。
}
3.拉链法:将产生冲突的元素，用一张链表保存起来
字符串hash
简单来说，就是将一个字符串转为一个唯一的数字对应。
假设字符串是由大写字母，小写字母，数字组成，实现方法是将其看作62进制，其中大写字母（0-25），小写字母（26-51）数字（52-61）
代码实现如下
int change(string a)
{
int rel=0;
int n=a.length();
for(int i=0;i<n;i++)
{
if(a[i]>='A'&&a[i]<='Z')
{
rel=rel*62+(a[i]-'A');//为什么这么写，相当于将0位看为最高位
}
else if(a[i]>='a'&&a[i]<='z')
{
rel=rel*62+(a[i]-'a')+26;
}
else
{
rel=rel*62+(a[i]-'0')+52;
}
}
return rel;
}
若数字只出现在字符串末尾，可以在最后拼接上字符串；
id=id*10+s[n-1]-‘0’；
给出N个字符串，再给出M个查询字符串，问M个字符串在N中出现的次数,
注意字符串的长度不能太长，否则数组放不下
int n,m;
int hash[10000]={0};
cin>>n>>m;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
int key=change(s);
hash[key]++;
cout<<key<<endl;
}
for(int i=0;i<m;i++)
{
cin>>s;
int key=change(s);
cout<<hash[key]<<endl;
}
1084 Broken Keyboard
检查数字键，字母键，和空格键是否坏掉。
由于结果最后输出大写，可以将小写字母全部转为大写字母，若存在该字母，则hash值++，hash[200]即可
string s,s1;
cin>>s>>s1;
int hash[130]={0};
for(int i=0;i<s.length();i++)//将小写字母看为大写字母处理
{
if(s[i]>='a'&&s[i]<='z')
{
hash[s[i]-32]++;
}
else
{
hash[s[i]]++;
}
}
for(int i=0;i<s1.length();i++)
{
if(s1[i]>='a'&&s1[i]<='z')
{
hash[s1[i]-32]--;
}
else
{
hash[s1[i]]--;
}
}
for(int i=0;i<s.length();i++)
{
if(s[i]>='a'&&s[i]<='z'&&hash[s[i]-32]>0)
{
printf("%c",s[i]-32);
hash[s[i]-32]=0;
}
else if(hash[s[i]]>0)
{
printf("%c",s[i]);
hash[s[i]]=0;
}
}
1033 旧键盘打字
注意点：第一行可能为空行，所以用cin会有一个测试点过不去，cin读取不了空行，getline可以读取空行
string s,s1;
int hash[130]={0};
getline(cin,s);
getline(cin,s1);
bool flag=true;
for(int i=0;i<s.length();i++)
{
if(s[i]=='+')
flag=false;
if(s[i]>='a'&&s[i]<='z')
{
hash[s[i]]++;
hash[s[i]-32]++;
}
else if(s[i]>='A'&&s[i]<='Z')
{
hash[s[i]]++;
hash[s[i]+32]++;
}
else
{
hash[s[i]]++;
}
}
for(int i=0;i<s1.length();i++)
{
if(s1[i]>='A'&&s1[i]<='Z'&&flag==true&&hash[s1[i]]==0)
{
printf("%c",s1[i]);
}
else if(hash[s1[i]]==0&&(s1[i]<'A'||s1[i]>'Z'))
{
printf("%c",s1[i]);
}
}
cout<<endl;
1038 统计同成绩学生
简单的hash
int main() {
int hash[102]={0};
int n,k;
cin>>n;
for(int i=0;i<n;i++)
{
int input;
cin>>input;
hash[input]++;
}
cin>>k;
for(int i=0;i<k;i++)
{
int check;
cin>>check;
if(i==0)
printf("%d",hash[check]);
else
printf(" %d",hash[check]);
}
system("pause");
}
1092 To Buy or Not to Buy
记录商店的颜色，用hash开始查找，若存在则使need-1；若need为0，代表全部都有，若need不为0，则代表还少这么多
string s,s1;
getline(cin,s);
getline(cin,s1);
int hash[130]={0};
int n=s.length();
int n1=s1.length();
int need=n1;
for(int i=0;i<n;i++)
{
hash[s[i]]++;
}
for(int i=0;i<n1;i++)
{
if(hash[s1[i]]>0)
{
hash[s1[i]]--;
need--;
}
}
if(need==0)
{
cout<<"Yes"<<" "<<n-n1;
}
else
{
cout<<"No"<<" "<<need;
}
最多出现的字母
注意：
1.不区分大小写
2.出现次数相同按照字典顺序比较，直接比较字母即可
string s;
getline(cin,s);
int max=0;//动态统计最大最小值
int hash[130]={0};
for(int i=0;i<s.length();i++)//只处理大小写字母
{
if(s[i]>='A'&&s[i]<='Z')//由于只输出小写字母，将大写字母当作小写字母处理
{
hash[s[i]+32]++;
if(hash[s[i]+32]>hash[max])
{
max=s[i]+32;
}
else if(hash[s[i]+32]==hash[max]&&s[i]+32<max)//若相等按照字典顺序处理
{
max=s[i]+32;
}
}
else if(s[i]>='a'&&s[i]<='z')
{
hash[s[i]]++;
if(hash[s[i]]>hash[max])
{
max=s[i];
}
else if(hash[s[i]]==hash[max]&&s[i]<max)
{
max=s[i];
}
}
}
printf("%c %d",max,hash[max]);
1043 输出PATest
复习的时候用了while1的写法，在循环里面判断这几个字母是否都是0
之前写的时候用了两层for循环，这几个字母最多就是输入字符串的长度
char input[6]={'P','A','T','e','s','t'};
string s;
getline(cin,s);
int hash[130]={0};
for(int i=0;i<s.length();i++)
{
hash[s[i]]++;
}
for(int i=0;i<s.length();i++)//字母个数最多就这么多
{
for(int j=0;j<6;j++)
{
if(hash[input[j]]>0)
{
printf("%c",input[j]);
hash[input[j]]--;
}
}
}
1047编程团体赛
int n;
cin>>n;
int hash[1200]={0};
int max=0;
for(int i=0;i<n;i++)//动态记录最大的编号
{
int term,id,grade;
scanf("%d%d%d",&term,&id,&grade);
hash[term]+=grade;
if(hash[term]>hash[max])
{
max=term;
}
}
cout<<max<<" "<<hash[max]<<endl;
1041 Be Unique
int n;
cin>>n;
vector<int> input;
int hash[10010]={0};
for(int i=0;i<n;i++)//统计个数
{
int k;
scanf("%d",&k);
input.push_back(k);
hash[k]++;
}
int i;
for( i=0;i<n;i++)
{
if(hash[input[i]]==1)
{
printf("%d",input[i]);
break;
}
}
if(i==n)
cout<<"None";
