首页 > 代码库 > 华为练习题--社交好友判断

华为练习题--社交好友判断

2024-07-16 01:57:15   219人阅读

好友关系管理
描述:

现有一个社交网站，其好友推荐策略为：用户A和用户B不是好友，当二人的共同好友数量超过好友推荐阈值m时，就向A和B分别推荐为彼此好友。 

本题任务为：对设定的m值，给定一组用户及各自好友列表，对这一组用户，反复自动应用上述好友推荐策略后（假设每次推荐都被采纳），求指定用户的最终好友列表。 

注：好友关系是双向的，即：如果用户A是用户B的好友，那么用户B一定也是用户A的好友。 

 

写一个程序，在社交网络中实现：

1）初始化社交网络 

2）创建用户 

3）增加指定两个用户之间的好友关系

4）反复自动应用好友推荐策略后，获取某个用户的好友数量 

5）反复自动应用好友推荐策略后，判断某两个用户间是否存在好友关系 

    

说明：

1、一个用户有且只有一个名字，且不存在重名 

2、自己和自己不存在好友关系 

3、用户名字大小写敏感 

4、用户名字字符串长度范围为[1..20]

5、用户总数小于100个

 

运行时间限制:无限制
内存限制:无限制
输入:
五个整数，好友推荐阈值P，创建用户数量m，增加指定两个用户之间的好友关系数量M，查询某个用户的好友数量n，查询指定两个用户是否是好友N字符串，每个数据一行，按到上面的顺序依次输入数据，共m+M+n+N行字符串
字符串，每个一行，共m+M+n+N行字符串

 

输出:
输出用户的好友数量，共n个，每个一行；如果用户不存在，输出-1，否则输出好友数量。样例中的用户Jack、Peter、Tom的好友数量都是2个。
输出指定两个用户是否是好友，共N个，每个一行，如果是输出0，否则输出-1。样例中的用户Jack与Peter、Peter与Tom、Jack与Tom都是好友关系，所有输出0。

 

样例输入:
2 3 3 3 3 //好友推荐阈值2，用户数量为3，增加知道两个用户之间的好友关系数量M， //查询某个用户的好友数量3，查询指定两个用户是否是好友N字符串
 Jack 
 Peter 
 Tom //输入了三个用户
 Jack Peter 
 Peter Tom 
 Jack Tom //增加了三个好友关系
 Jack
 Peter 
 Tom //查询了这三个用户的好友数量
 Jack Peter 
 Peter Tom 
 Jack Tom //查询了这三个好友关系是否存在
 样例输出: 

        
样例输出:
2 //Jack几个好友，这里就用到了阈值
2 //Peter几个好友
2 
0 //Jack Peter是否好友
0 //Peter Tom是否好友
0 //Jack Tom是否好友

class Userinfo{		//用户
	private String uname;	//用户名
	private Set<Userinfo> friends = null;
	
	public Userinfo(String uname) {
		super();
		this.uname = uname;
	}
	
	public String getUname() {
		return uname;
	}
	public void setUname(String uname) {
		this.uname = uname;
	}
	public Set<Userinfo> getFriends() {
		return friends;
	}
	public void setFriends(Set<Userinfo> friends) {
		this.friends = friends;
	}
	public void addFriend(Userinfo userinfo){
		if(this.friends==null){
			this.friends = new HashSet<Userinfo>();
		}
		this.friends.add(userinfo);
	}
	@Override
	public boolean equals(Object obj){
		if(!(obj instanceof Userinfo))
			return false;
		Userinfo user = (Userinfo)obj;
		if(!user.getUname().equals(this.uname))
			return false;
		return true;
	}
	@Override
	public int hashCode(){
		int length = this.uname.length();
		for(int i = 0; i< this.uname.length(); i++){
			char ch = this.uname.charAt(i);
			length = length + i * (int)ch;
		}
		return length;	
	}
}

public class Main32 {
	public static Set<Userinfo> set = new HashSet<Userinfo>();// 当前系统中的用户集合
	public static int P;// 好友推荐阈值P
	public static int m;// 创建用户数量m
	public static int M;// 增加指定两个用户之间的好友关系数量M
	public static int n;// 查询某个用户的好友数量n
	public static int N;// 查询指定两个用户是否是好友N字符串
	public static int count = 2;
	static Set<Userinfo> friend = null;

	public static void initial() {
		Scanner scan = new Scanner(System.in);
		P = scan.nextInt();
		m = scan.nextInt();
		M = scan.nextInt();
		n = scan.nextInt();
		N = scan.nextInt();
		for (int i = 0; i < m; i++) {// m个用户名
			String uname = scan.next();
			addUser(uname);
		}
		for (int i = 0; i < M; i++) {// M个用户关系
			String r1 = scan.next();
			String r2 = scan.next();
			addRelation(r1, r2);
		}
		int[] nn = new int[n]; // 存储好友数量
		for (int i = 0; i < n; i++) {// n个用户的好友数量
			String uname = scan.next();
			nn[i] = getCount(uname);
		}
		int[] nN = new int[N];
		for (int i = 0; i < N; i++) {// 判断这几组是否好友
			String s1 = scan.next();
			String s2 = scan.next();
			nN[i] = isFriend(s1, s2);
		}
		for (int i = 0; i < n; i++) {
			System.out.println(nn[i]);
		}
		for (int i = 0; i < N; i++) {
			System.out.println(nN[i]);
		}
	}

	/**
	 * 返回用户好友数量
	 * 
	 * @return
	 */
	public static int getCount(String uname) {
		Userinfo user = findByName(uname);
		friend = new HashSet<Userinfo>();
		getAll(user);
		user.setFriends(friend);
		return friend.size();
	}

	public static void getAll(Userinfo user) {
		Set<Userinfo> friends = user.getFriends();
		if (friends != null) {
			for (Userinfo userinfo : friends) {
				if (!friend.contains(userinfo))
					friend.add(userinfo);
				if (count < P) {
					count++;
					getAll(userinfo);
					count--;
				}
				if (count >= P) {
					return;
				}
			}
		}
	}

	public static boolean addUser(String uname) {
		if (!atSet(uname)) {
			set.add(new Userinfo(uname));
		} else {
			return false;
		}
		return true;
	}

	public static boolean atSet(String uname) {
		for (Userinfo userinfo : set) {
			if (userinfo.getUname().equals(uname)) {
				return true;
			}
		}
		return false;
	}

	public static Userinfo findByName(String uname) {
		for (Userinfo userinfo : set) {
			if (userinfo.getUname().equals(uname)) {
				return userinfo;
			}
		}
		return null;
	}

	public static void addRelation(String uname, String uname2) {
		Userinfo user1 = findByName(uname);
		Userinfo user2 = findByName(uname2);
		user1.addFriend(user2);
		user2.addFriend(user1);

	}

	public static int isFriend(String uname, String uname2) {
		Userinfo user1 = findByName(uname);
		Userinfo user2 = findByName(uname2);

		return isFriend(user1, user2);
	}

	public static int isFriend(Userinfo u1, Userinfo u2) {

		Set<Userinfo> friends1 = u1.getFriends();
		Set<Userinfo> friends2 = u2.getFriends();
		if (friends1 != null) {
			for (Userinfo user : friends1) {
				if (user.equals(u2))
					return 0;
				if (count < P) {
					count++;
					isFriend(user, u2);
					count--;
				}
			}
		}
		if (friends2 != null) {
			for (Userinfo user : friends2) {
				if (user.equals(u1))
					return 0;
				if (count < P) {
					count++;
					isFriend(user, u1);
					count--;
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		initial();
	}

}




阈值大于2时，出错，估计是递归设计不合理！先留着，有新思路再做。
































        

            
                
                  
                
                

                    联系

                    我们