P14375.社交网络相同爱好好友查询(200分)

1000ms

Tried: 15

Accepted: 2

Difficulty: 6

所属公司 : 华为od

算法与标签>BFS

题目内容

在一个社交网络中，用户之间通过"关注"关系形成有向图。每个用户有两个属性：

用户 $ID$ （整数字符串）
兴趣标签列表（字符串数组）

现在需要实现一个函数，查询在指定用户 $k$ 跳内（ $k$ 度关系内）其他用户的兴趣和给定用户兴趣相符的用户 $ID$ 列表（不含自己）。

注意：兴趣相符是指两个用户的兴趣列表有交集。

实现函数： $queryFriends(nodes, relations, myId, maxHop)$

输入参数

$nodes$ $n o d es$ - 用户节点数据
- 类型：整数二维数组/向量
- 每行表示一个用户，包含：[ $id$ , 兴趣 $1$ , 兴趣 $2$ , ...]
- 示例：[" $0$ ", " $music$ ", " $reading$ "] 表示用户 $0$ ，有 $2$ 个兴趣： $music$ 和 $reading$
- 所有用户 $ID$ 是 $0$ 到 $n-1$ 的连续整数对应的字符串
$relations$ $re l a t i o n s$ - 关注关系
- 类型：整数二维数组/向量
- 每行表示一个关注关系：[关注者 $ID$ , 被关注者 $ID$ ]
- 示例：[" $0$ ", " $1$ "] 表示用户 $0$ 关注了用户 $1$
$myId$ - 起始用户 $ID$ ，示例：" $0$ "
$maxHop$ - 最大跳数 $k$ ，示例： $2$

返回值

内容：所有满足条件的用户 $ID$ 及共同的兴趣列表，如[[" $0$ ", " $music$ ", " $reading$ "],[" $1$ ", " $reading$ "]]
格式 $1$ ：不同用户之间按以下规则排序：

按与起始用户的最短距离从小到大排序

距离相同的用户，按ID对应整数值进行从小到大排序
格式 $2$ ：对于具体某用户与起始用户的共同兴趣列表按以下规则排序：按照 $ascii$ 码序从小到大排序
如果没有满足条件的用户，返回空数组

约束条件

用户数 $n: 1 ≤ n ≤ 10^4$ ，可认为用户的 $id$ 字符串对应整数范围符合该条件
关注关系数 $m: 0 ≤ m ≤ 2×10^4$ ，若关系任一端包含不存在的点应该自动忽略，不影响原始查询诉求
最大跳数 $k: 1 ≤ k ≤ 100$ ，大于最大跳数，按照上限 $100$ 对待
每个用户最多 $10$ 个兴趣标签，可认为所有用户的兴趣个数符合该条件
给定查询条件中的起始用户 $ID$ 一定存在

样例1

输入

[["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$ "之前。

样例2

输入

[["0","music"],["1","music"],["2","music"],["3", "music"],["4","music"]],[["0","1"],["1","2"],["2","3"],["3","4"]],"0",1

输出

[["1","music"]]

说明

所有用户都满足兴趣条件，但是跳数限制在 $1$ 跳内，因此仅用户" $1$ "满足条件

样例3

输入

[["0","music"]],[],"0",2

输出

[]

说明

不存在满足条件的结果，返回空数组

输入

预期输出（选填）

解题思路

P14375.社交网络相同爱好好友查询(200分)

题目内容

输入参数

返回值

约束条件

样例1

样例2

样例3

Status

Development

Support

About