@[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;
}