【MOOC-浙大数据结构】第十一周的编程作业——查找

灰太狼 2024-04-17 06:01 67阅读 0赞

1.**[电话聊天狂人][Link 1]**

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int main()
    {
        map<string,int> mp;
        string str1,str2,s;
        int n,i,maxn=-999,ansnum,maxnnum=0;
        cin>>n;
        for(i=0;i<n;i++)
    	{
            cin>>str1>>str2;
            mp[str1]++;
            mp[str2]++;
        }
        map<string,int>::iterator it;
        for(it=mp.begin();it!=mp.end();it++)
    	{
            if(it->second>maxn)
    		{
                s=it->first;
                ansnum=it->second;
                maxn=it->second;
            }
        }
        for(it=mp.begin();it!=mp.end();it++)
    	{
            if(it->second==maxn)
            maxnnum++;
        }
        cout<<s<<" "<<ansnum;
        if(maxnnum>1)
        cout<<" "<<maxnnum;
    }

2.**[Hashing][]**

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int a[10050];
    bool prime(int x)
    {
    	if(x==1) return false;
    	if(x==2||x==3) return true;
    	for(int i=2;i<=sqrt(x);i++)
    	{
    		if(x%i==0)return false;
    	}
    	return true;
    }
    int main()
    {
    	int maxn,n,x,i,j,k=0;
    	memset(a,0,sizeof a);
    	scanf("%d%d",&maxn,&n);
    	while(!prime(maxn)) maxn++;//找到大于maxn的素数 
    	//printf("%d\n",maxn);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		int flag=1;
    		for(j=0;j<maxn;j++)
    		{
    			int pos=(x+j*j)%maxn;
    			if(a[pos]==0)
    			{
    				flag=0;
    				a[pos]=x;
    				if(k)printf(" ");
    				printf("%d",pos);
    				k++;
    				break;
    			}
    		}
    		if(flag)
    		{
    			if(k)printf(" ");
    			printf("-");
    			k++;
    		}
    	}
    }

3.**[QQ帐户的申请与登陆][QQ]**

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int main()
    {
    	int n;
    	string a3,a2;
    	char a1;
    	map<string,string> Q;
    	scanf("%d",&n);
    	while(n--)
    	{
    		cin>>a1>>a2>>a3;
    		if(a1=='N')
    		{
    			if(Q.find(a2)==Q.end())
    			{
    				Q[a2]=a3;
    				cout<<"New: OK"<<endl;
    			}
    			else
    			cout<<"ERROR: Exist"<<endl;
    		}
    		else
    		{
    			if(Q.find(a2)==Q.end())
    			cout<<"ERROR: Not Exist"<<endl;
    			else
    			{
    				map<string,string>::iterator it;
    				it=Q.find(a2);
    				if(it->second==a3)
    				cout<<"Login: OK"<<endl;
    				else
    				cout<<"ERROR: Wrong PW"<<endl;
    			}
    		}
    	}
    }

4.**[Hashing - Hard Version][]**

#include <stdio.h>
    #include <string.h>
    #include <string>
    #include <map>
    #include <vector>
    #include <queue>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #define INF 0x3f3f3f3f
    using namespace std;
    vector<int> v[10005];//单向图 - 存的是下标,不是数值 
    int a[10005];
    int degree[10005];//入度
    struct cmp 
    {
        bool operator()(int i,int j) 
    	{
            return a[i]>a[j];
        }
    };
    priority_queue<int,vector<int>,cmp > q;
    int main()
    {
    	int n,i,j,x;
    	memset(degree,0,sizeof degree);
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&a[i]);
    		if(a[i]>=0)
    		{
    			x=a[i]%n;
    			degree[i]=(i+n-x)%n;
    			if(degree[i]!=0)//发生冲突 
    			{
    				for(j=0;j<=degree[i];j++)
    				v[(x+j)%n].push_back(i);	
    			}
    			else
    			q.push(i);
    		}
    	}
    	//for(i=0;i<n;i++)
    	//printf("%d : %d\n",a[i],degree[i]);
    	int f=0;//控制空格输出 
    	while(!q.empty())
    	{
    		int u=q.top();	
    		q.pop();
    		
    		if(f)printf(" ");
    		printf("%d",a[u]);
    		f++;
    			
    		for(i=0;i<v[u].size();i++)
    		{
    			degree[v[u][i]]--;
    			if(degree[v[u][i]]==0)
    			q.push(v[u][i]);
    		}
    	}
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1161486773318311936
[Hashing]: https://pintia.cn/problem-sets/1134360184290500608/problems/1161486773318311937
[QQ]: https://pintia.cn/problem-sets/1134360184290500608/problems/1161486773318311938
[Hashing - Hard Version]: https://pintia.cn/problem-sets/1134360184290500608/problems/1161486773318311939