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

华为OD新系统机试真题 华为OD新系统上机考试真题 5月13号 200分题型

本题更多语言题解，可点击查看:华为OD机试新系统真题 - 社交网络相同爱好好友查询(C/C++/Py/Java/Js/Go)题解

题目内容

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

• 用户 $ID$（整数字符串）

• 兴趣标签列表（字符串数组）
  现在需要实现一个函数，查询在指定用户 $k$ 跳内（$k$ 度关系内）其他用户的兴趣和给定用户兴趣相符的用户 $ID$ 列表（不含自己）。
  注意：兴趣相符是指两个用户的兴趣列表有交集。

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

输入参数

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$

返回值

• 内容：所有满足条件的用户 $ID$ 及共同的兴趣列表，如[[“$0$”, “$music$”, “$reading$”],[“$1$”, “$reading$”]]
• 格式 $1$：不同用户之间按以下规则排序：
  按与起始用户的最短距离从小到大排序
  距离相同的用户，按ID对应整数值进行从小到大排序
• 格式 $2$：对于具体某用户与起始用户的共同兴趣列表按以下规则排序： 按照 $ascii$ 码序从小到大排序
• 如果没有满足条件的用户，返回空数组

约束条件

1. 用户数 $n:1\le n\le 10^4$，可认为用户的 $id$ 字符串对应整数范围符合该条件
2. 关注关系数 $m:0\le m\le 2\times 10^4$，若关系任一端包含不存在的点应该自动忽略，不影响原始查询诉求
3. 最大跳数 $k:1\le k\le 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$” 出发兴趣相同（$2$ 跳内）可以匹配到用户"$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

1. 先提取出每个用户的兴趣爱好，根据id进行保存
2. 将用户作为节点，关注关系看作有向边。根据输入关注关系创建对应邻接表。
3. 指定k跳级就是用户之间的距离，用户之间的距离可以使用最短路算法或者BFS算法实现，下面代码利用BFS计算其它用户与指定用户的距离。使用dist数组存储其它用户与指定用户距离。具体逻辑为
   1. 初始将myId加入队列中,更新dist[myId] = 0
   2. 每次从队列中取出队首元素current，更新相邻节点的距离,对应节点node处理如下：
      • 如果dist[node] != -1，说明之前已访问，不做处理
      • dist[node] == 1的情况，更新对应距离为dist[node] = dist[current] + 1,如果dist[node] >= maxHop不加入队列(本题距离大于maxHop可认为不可达)。否则加入队列中。
   3. 重复执行2的逻辑直到队列为空。
4. 利用dist找到可达用户，并且提取出拥有公共爱好的用户加入结果数组中。共同爱好需要进行排序
5. 按照题目要求利用dist进行自定义按与起始用户的最短距离从小到大排序 距离相同的用户，按ID对应整数值进行从小到大排序规则排序。

c++

#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<algorithm> 
#include<cmath>
#include<map>
#include<queue>
using namespace std;

// 通用 切割函数 函数 将字符串str根据delimiter进行切割
vector<string> split(const string& str, const string& delimiter) {
    vector<string> result;
    size_t start = 0;
    size_t end = str.find(delimiter);
    while (end != string::npos) {
        result.push_back(str.substr(start, end - start));
        start = end + delimiter.length();
        end = str.find(delimiter, start);
    }
    // 添加最后一个部分
    result.push_back(str.substr(start));
    return result;
}

vector<string> findSameLike(vector<string>& a, vector<string>& b) {
    if (a.empty() || b.empty()) {
        return {};
    }
    vector<string> res;
    for (int i = 0; i < a.size(); i++) {
        string item = a[i];
        for (int j = 0; j < b.size(); j++) {
            if (b[j] == item) {
                res.push_back(item);
            }
        }
    }
    return res;
}


vector<vector<string>> queryFriends(vector<vector<string>>& nodes, vector<vector<string>>& relations, string myId, int maxHop) {
    int n = nodes.size();
    // 限制不超过100
    maxHop = min(maxHop, 100);


    vector<vector<int>> graph(n);
    // 根据关注关系，建表
    for (auto& relation : relations) {
        int u = stoi(relation[0]);
        int v = stoi(relation[1]);
        // 存在不存在的点
        if (u < 0 || v < 0 || u > n - 1 || v > n - 1) {
            continue;
        }
        graph[u].push_back(v);

    }

    // 映射每个用户的爱好
    vector<vector<string>> like(n);
    for (auto &node : nodes) {
        string id = node[0];
        int idValue = stoi(id);
        for (int j = 1; j < node.size(); j++) {
            like[idValue].push_back(node[j]);
        }
    }
    
    // 处于指定用户跳数
    vector<int> dist(n, -1);
    int myIdValue = stoi(myId);
    //指定用户不存在爱好情况，肯定没有结果
    if (like[myIdValue].empty()) {
        return {};
    }
    
    // 使用BFS求跳数 
    queue<int> q;
    q.push(myIdValue);
    dist[myIdValue] = 0;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (auto& v : graph[current]) {
            if (dist[v] != -1) {
                continue;
            }
            dist[v] = dist[current] + 1;
            if (dist[v] < maxHop) {
                q.push(v);
            } 
        }
    }


    vector<vector<string>> res;
    // 找出具备相同爱好并且在指定跳内的结果
    for (int i = 0; i < n; i++) {
        if (dist[i] == -1) {
            continue;
        }
        if (i == myIdValue) {
            continue;
        }
        vector<string> sameLike = findSameLike(like[i], like[myIdValue]);
        if (sameLike.empty()) {
            continue;
        }

        // 将爱好升序
        sort(sameLike.begin(), sameLike.end());
        vector<string> item;
        item.push_back(to_string(i));
        for (string s : sameLike) {
            item.push_back(s);
        }
        res.push_back(item);
    }

    // 自定义进行排序
    sort(res.begin(), res.end(), [&](vector<string>&a , vector<string>& b) {
        int id1 = stoi(a[0]);
        int id2 = stoi(b[0]);
        if (dist[id1] == dist[id2]) {
            return id1 < id2;
        } 
        return dist[id1] < dist[id2];
    });
    
    return res;
}

int main() {
    string input1,input2,myId,maxHopStr;
    getline(cin, input1);
    getline(cin, input2);
    getline(cin, myId);
    getline(cin, maxHopStr);
    
    vector<vector<string>> nodes;
    vector<string> tmp;
    if (!input1.empty()) {
        tmp = split(input1, " ");
        for (int i = 0; i < tmp.size(); i++) {
            nodes.push_back(split(tmp[i], ","));
        }
    } 
    vector<vector<string>> relations;
    if (!input2.empty()) {
        tmp = split(input2, " ");
        for (int i = 0; i < tmp.size(); i++) {
            relations.push_back(split(tmp[i], ","));
        }
    }
    
    vector<vector<string>> res = queryFriends(nodes, relations, myId, stoi(maxHopStr));

    // 输出结果
    for (int i = 0; i < res.size(); i++) {
        vector<string> current = res[i];
        for (int j = 0; j < current.size(); j++) {
            if (j != 0) {
                cout << ",";
            }
            cout << current[j];
        }
        cout << endl;
    }
}

JAVA

import java.util.*;

public class Main {

    public static List<List<String>> queryFriends(
            List<List<String>> nodes,
            List<List<String>> relations,
            String myId,
            int maxHop) {

        int n = nodes.size();

        // 限制不超过100
        maxHop = Math.min(maxHop, 100);

        // 根据关注关系，建表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for (List<String> r : relations) {
            int u = Integer.parseInt(r.get(0));
            int v = Integer.parseInt(r.get(1));

            // 存在不存在的点
            if (u < 0 || u >= n || v < 0 || v >= n) continue;

            graph.get(u).add(v);
        }

        // 映射每个用户的爱好
        List<List<String>> like = new ArrayList<>();
        for (int i = 0; i < n; i++) like.add(new ArrayList<>());

        for (List<String> node : nodes) {
            int id = Integer.parseInt(node.get(0));
            for (int i = 1; i < node.size(); i++) {
                like.get(id).add(node.get(i));
            }
        }

        // 处于指定用户跳数
        int[] dist = new int[n];
        Arrays.fill(dist, -1);

        int myIdValue = Integer.parseInt(myId);

        // 指定用户不存在爱好情况，肯定没有结果
        if (like.get(myIdValue).isEmpty()) {
            return new ArrayList<>();
        }

        // 使用BFS求跳数
        Queue<Integer> q = new LinkedList<>();
        q.offer(myIdValue);
        dist[myIdValue] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int v : graph.get(cur)) {
                if (dist[v] != -1) continue;

                dist[v] = dist[cur] + 1;

                if (dist[v] < maxHop) {
                    q.offer(v);
                }
            }
        }

        List<List<String>> res = new ArrayList<>();

        // 找出具备相同爱好并且在指定跳内的结果
        for (int i = 0; i < n; i++) {
            if (dist[i] == -1) continue;
            if (i == myIdValue) continue;

            List<String> sameLike = new ArrayList<>();

            for (String a : like.get(i)) {
                for (String b : like.get(myIdValue)) {
                    if (a.equals(b)) sameLike.add(a);
                }
            }

            if (sameLike.isEmpty()) continue;

            // 将爱好升序
            Collections.sort(sameLike);

            List<String> item = new ArrayList<>();
            item.add(String.valueOf(i));
            item.addAll(sameLike);

            res.add(item);
        }

        // 自定义进行排序
        res.sort((a, b) -> {
            int id1 = Integer.parseInt(a.get(0));
            int id2 = Integer.parseInt(b.get(0));

            if (dist[id1] == dist[id2]) return id1 - id2;
            return dist[id1] - dist[id2];
        });

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String input1 = sc.nextLine();
        String input2 = sc.nextLine();
        String myId = sc.nextLine();
        int maxHop = Integer.parseInt(sc.nextLine());

        List<List<String>> nodes = new ArrayList<>();
        List<List<String>> relations = new ArrayList<>();

        
        if (!input1.isEmpty()) {
            for (String s : input1.split(" ")) {
                nodes.add(Arrays.asList(s.split(",")));
            }
        }

        if (!input2.isEmpty()) {
            for (String s : input2.split(" ")) {
                relations.add(Arrays.asList(s.split(",")));
            }
        }

        List<List<String>> res = queryFriends(nodes, relations, myId, maxHop);

        for (List<String> r : res) {
            System.out.println(String.join(",", r));
        }
    }
}