共同好友推荐java_算法题之好友推荐

大家好，我是讯享网，很高兴认识大家。

题目要求：

有n个人，每个人都有各自的好友列表。给定一个阈值p，当A和B的共同好友数超过p则推荐A和B为好友。请实现自动推荐直到没有好友可以推荐(每次推荐默认同意，即一定成为好友)，然后进行一些查询。

查询1：A的好友数有几个？如果A不在这n个里面，输出-1，否则输出好友数；

查询2：A和B是好友吗？如果是则输出0，否则输出-1。

输入：p n m x y

p为阈值，n为人数，m为初始时的好友，x为查询1的个数，y为查询2的个数

注： - 如果A是B的好友，B一定是A的好友； - 每个人的人名用不超过20个字符的字符串表示，没有重名的人； - 人数不超过100.

输入示例：

2 3 3 3 3

A B

B C

A C

A B

C A

B C

应输出：

我的思路：

1.根据输入的好友数量N，建立一个N*N的关系矩阵，1表示为好友，0表示非好友关系。这样做的好处是便于保存和修改好友关系。注意点：每次修改时要对m,n和n,m两个位置的元素进行修改；对第i行遍历时从第i+列开始即可。

2.好友推荐处理过程就是对关系矩阵的处理，遍历矩阵每一行，当为非好友时，通过矩阵算出共同好友数；为好友时，跳过；当共同好友数超过阈值时将值设为1。直到关系矩阵不再被改变为止，此时已无可推荐好友了。

3.基于处理后的关系矩阵，根据输入的查询进行计算即可。

#include#include#include#include//用到其中的find()函数，返回迭代器或指针

using namespacestd;int friendnum(vector &R,vector &namelist, string name,intN)

{int loc=find(namelist.begin(),namelist.end(),name)-namelist.begin();int count=0;if(loc>N-1)

count=-1;else{for(int i=0;i

count++;

}returncount;

}int isfriend(vector &R,vector &namelist, string name1,string name2,intN)

{int loc1=find(namelist.begin(),namelist.end(),name1)-namelist.begin();int loc2=find(namelist.begin(),namelist.end(),name2)-namelist.begin();int count=-1;if(loc1>N-1||loc2>N-1)

count=-1;else{if(R[loc1*N+loc2]==1)

count=0;

}returncount;

讯享网

}voidmain()

{while(1)

{

vectornamelist;stringnametemp;intP,N,M,X,Y;

cin.clear();

cin.sync();

cin>>P>>N>>M>>X>>Y;

vector R(N*N,0);//建立关系矩阵，默认为0，非好友

int n=N;//人数

while(n--)//建立姓名列表

{

cin>>nametemp;

namelist.push_back(nametemp);

}int m=M;stringname1,name2;intname1_it,name2_it;while(m--)//填充关系矩阵

{

cin>>name1>>name2;

name1_it=find(namelist.begin(),namelist.end(),name1)-namelist.begin();//注意string.find()返回的是下标，而find()返回的是迭代器,用find()函数在容器中获得下标方法find(vec_aa.begin(),vec_aa.end(),2)-vec_aa.begin();没有找到时返回值超过边界。

name2_it=find(namelist.begin(),namelist.end(),name2)-namelist.begin();//似乎string不需要用到迭代器，可返回下标，也可使用下标。string.back()是什么鬼？

R[name1_it*N+name2_it]=1;

R[name2_it*N+name1_it]=1;

}//显示初始好友关系矩阵。1：好友；2：非好友//for(int i=0;i

int flag=1;while(flag)

{

flag=0;//用于判断是否结束推荐

for(int i=0;i

{for(int j=i+1;j

{if(R[N*i+j]!=1)//不是好友

{//判断是否符合推荐阈值

int count=0;for(int k=0;k

count++;if(count>=P)//达到阈值

{

R[N*i+j]=1;//成为相互间的好友

R[N*j+i]=1;//修改关系矩阵

}

flag=1;//有推荐改动，继续推荐循环

}

}//显示好友推荐完成后的好友关系矩阵。1：好友；2：非好友//for(int i=0;i::iterator loc=find(vec_aa.begin(),vec_aa.end(),2)-vec_aa.begin();

//int loc=find(vec_aa.begin(),vec_aa.end(),2)-vec_aa.begin();//cout<

}//测试集//输入：//2 3 3 3 3//A//B//C//A B//B C//A C//A//B//C//A B//C A//B C//应输出：//2//2//2//0//0//0

1.find()和string.find()区别：algorithm库中的find()返回的是迭代器，输入三个参数，开始和结束的迭代器，待寻找值。获得下标值得方式是find(.begin(),.end(),xx)-.begin()；string.find()返回的是下标值。

共同好友推荐java_算法题之好友推荐

相关推荐