把用户和关注关系看成一张有向图。关系 [a,b] 表示从用户 a 可以沿一条有向边到达用户 b。
需要查询从 myId 出发,最短距离不超过 maxHop 的用户,并筛选出与 myId 至少有一个共同兴趣的用户。
处理步骤如下:
nodes 建立用户到兴趣集合的映射。在一个社交网络中,用户之间通过"关注"关系形成有向图。每个用户有两个属性:
现在需要实现一个函数,查询在指定用户 k 跳内(k 度关系内)其他用户的兴趣和给定用户兴趣相符的用户 ID 列表(不含自己)。
注意:兴趣相符是指两个用户的兴趣列表有交集。
实现函数:queryFriends(nodes,relations,myId,maxHop)
内容:所有满足条件的用户 ID 及共同的兴趣列表,如[["0", "music", "reading"],["1", "reading"]]
格式 1:不同用户之间按以下规则排序:
按与起始用户的最短距离从小到大排序
距离相同的用户,按ID对应整数值进行从小到大排序
格式 2:对于具体某用户与起始用户的共同兴趣列表按以下规则排序: 按照 ascii 码序从小到大排序
如果没有满足条件的用户,返回空数组
输入
[["0","music","sports"],["1","music","reading"],["2","music"],["3","play","music","sports"]],[["0","1"],["1","2"],["2","3"],["0","3"]],"0",2
输出
[["1","music"],["3","music","sports"],["2","music"]]
说明
从 ID="0" 出发兴趣相同(3 跳内)可以匹配到用户"1"、"2"、"3",同时用户"1"、"3"跳数少,因此用户"1"、"3"在用户"2"之前。,又因为"1"相比于"3"整数序靠前,因此用户"1"在用户"3"。用户"3"中,匹配到了多项爱好,根据字母序排列,"music"在"sports"之前。
输入
[["0","music"],["1","music"],["2","music"],["3", "music"],["4","music"]],[["0","1"],["1","2"],["2","3"],["3","4"]],"0",1
输出
[["1","music"]]
说明
所有用户都满足兴趣条件,但是跳数限制在 1 跳内,因此仅用户"1"满足条件
输入
[["0","music"]],[],"0",2
输出
[]
说明
不存在满足条件的结果,返回空数组