机试常用算法和题型-哈希专题

哈希专题

hash表的用法

#include <iostream>

using namespace std;

int main()
{

    int n,m;
    while(cin>>n>>m){
      //最好还是固定住值，不然会编译报错，初始化为0
        int hashTable[201]={0};
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
            hashTable[arr[i]]++;
        }
        for(int i=0;i<n;i++){
            if(hashTable[arr[i]]>1)
                cout<<hashTable[arr[i]]-1<<endl;
            else cout<<"BeiJu"<<endl;
        }
    }
    return 0;

}

hash表高阶用法，二维数组存放不同组的hash值

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int n,m,s[110],g[110],t[110];
    while(~scanf("%d",&n))
    {   
        for(int i=0;i<n;i++)
        {
            int z[110][2100]={0};
            scanf("%d",&m);
            for(int j=0;j<m;j++)
                scanf("%d",&s[j]);
            for(int j=0;j<m;j++)
            {
                scanf("%d",&g[j]);
                z[g[j]][s[j]]++;
            }
          //这里的排序算法，使用很是巧妙
            sort(s,s+m);
            sort(g,g+m);
            for(int j=0;j<m;j++)
            {//关键要落实到此处，输出第一个之后，每次都输出与前一个不同的数
                if(j==0||(j>0&&g[j]!=g[j-1]))
                {//输出格式也很关键
                    printf("%d={",g[j]);
                    for(int k=0;k<m;k++)
                    {
                        if(k==0||(k>0&&s[k]!=s[k-1]))
                        {
                            printf("%d=%d",s[k],z[g[j]][s[k]]);
                            if(k!=m-1&&s[k]!=s[m-1])
                                printf(",");
                        }
                    }
                    printf("}\n");
                }
            }
        }
    }
    return 0;
} 

hash结合字母表处理字符串的使用方法

//这个题的输出处理方式太强了
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{

    string str1,str2;
    while(getline(cin,str1)){
        int hashTable[26]={0};
        getline(cin,str2);
        for(int i=0;i<str2.size();i++){
            hashTable[str2[i]-'a']++;
        }
        for(int i=0;i<str1.size();i++){
            if(str1[i]!=' '&&hashTable[str1[i]-'a']!=0)
                {
                    str1.erase(i,1);
                    //这个减一必不可少，因为erase去除了当前的i，则原来的i+1向前移动，如果不向前移动，会错过检查原来的i+1
                    i=i-1;
                }

        }
        cout<<str1<<endl;
    }

    return 0;

}
//其实做的复杂了，可以更简单的，不用删除，控制输出即可
#include <cstdio>
#include <cstring>
int main()
{
    char s1[10010],s2[10010];
  //255表示全部字符的范围
    int flag[255];
    while(gets(s1))
    {
        memset(flag,0,sizeof(flag));
        gets(s2);
        for(int i=0;s2[i]!='\0';++i)
            flag[s2[i]]=true;
        for(int i=0;s1[i]!='\0';++i)
            if(flag[s1[i]]==false)
                printf("%c",s1[i]);
    }
    return 0;
}