# 社交网络相同爱好好友查询

2026 华为OD机试真题 5月13日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

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

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

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

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

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

2026 华为OD机试真题 5月13日华为OD上机新系统考试真题 100 分题型

输入描述

1. nodes - 用户节点数据

   • 类型：字符串二维数组/向量
   • 每行表示一个用户，包含：[id, 兴趣1, 兴趣2, ...]
   • 示例：["0", "music", "reading"] 表示用户 0，有 2 个兴趣：music 和 reading
   • 所有用户 ID 是 0 到 n-1 的连续整数对应的字符串

2. relations - 关注关系

   • 类型：字符串二维数组/向量
   • 每行表示一个关注关系：[关注者ID, 被关注者ID]
   • 示例：["0", "1"] 表示用户 0 关注了用户 1

3. myId - 起始用户 ID，示例："0"

4. maxHop - 最大跳数 k，示例：2

输入格式：一行，nodes、relations、myId、maxHop 用逗号分隔，例如： [["0","music","sports"],["1","music","reading"]],[["0","1"]],"0",2`

输出描述

• 内容：所有满足条件的用户 ID 及共同的兴趣列表，如 [["1","music"],["3","music","sports"]]

• 格式 1：不同用户之间按以下规则排序：

  • 按与起始用户的最短距离从小到大排序
  • 距离相同的用户，按ID对应整数值进行从小到大排序

• 格式 2：对于具体某用户与起始用户的共同兴趣列表按以下规则排序：

  • 按照 ASCII 码序从小到大排序

• 如果没有满足条件的用户，返回空数组 []

约束条件

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

输出

[]

说明

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

解题思路

核心思想

本题分为两个阶段：图搜索和集合匹配。

阶段一：BFS 多源/单源有向图遍历

• 构建邻接表（关注关系为有向边），对 myId 进行 BFS。
• 记录从 myId 到每个可达用户的最短距离（跳数），超过 maxHop 时停止扩展。
• 时间复杂度 O(n + m)，n 为用户数，m 为关注关系数。

阶段二：交集筛选与排序

• 对每个可达用户（不含自己），计算与 myId 的兴趣交集。
• 交集非空时，按 (距离, 用户ID整数) 升序排列结果；每行内兴趣按 ASCII 升序排列。
• 若无满足条件的用户，返回空数组。

复杂度分析

• 时间复杂度: O(n + m + n × avg_interests)，其中 avg_interests 为平均兴趣数，最多 10。
• 空间复杂度: O(n + m)，邻接表和