华为校招机试 - 找到内聚值最大的微服务群组（20240424）

朱雀 2024-05-06 23:25 6阅读 0赞

#### 在线OJ测试 ####

[题目详情 - 找到内聚值最大的微服务群组 - HydroOJ][- _ - HydroOJ]

####  ####

#### 题目描述 ####

开发团队为了调研微服务调用情况，对 n 个微服务调用数据进行了采集分析，微服务使用数字 0 至 n-1 进行编号。

给你一个下标从 0 开始的数组 edges，其中 edges\[i\] 表示存在一条从微服务 i 到微服务 edges\[i\] 的接口调用。

我们将形成 1 个环的多个微服务称为微服务群

*  一个微服务群组的所有微服务数量为 L
 *  能够访问到该微服务群组的微服务数量为 V
 *  这个微服务群组的内聚值 H = L - V

已知提供的数据中有 1 个或多个微服务群组，请按照内聚值 H 的结果从大到小的顺序对所有微服务群组（H 相等时，取环中最大的数进行比较）排序，

输出排在第一的微服务群组（输出时每个微服务群组输出的起始编号为环中最小的数）。

#### 输入描述 ####

入参分为两行输入：

*  第一行为：n，表示有 n 个微服务
 *  第二行为：数组edges，其中 edges\[i\] 表示存在一条从微服务 i 到微服务 edges\[i\] 的接口调用，数字以空格分隔

输入范围说明：

*  n == edges.length
 *  2 ≤ n ≤ 10^5
 *  0 ≤ edges\[i\] ≤ n-1
 *  edges\[i\] ≠ i

#### 输出描述 ####

输出排在第一的微服务群组的编号数组，按照环的访问顺序输出，起始编号为环中最小的数，数字以空格分隔

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">4<br> 3 3 0 2</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">0&nbsp;3&nbsp;2</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p><img alt="" height="271" src="https://img-blog.csdnimg.cn/direct/e99eaf1891ea4cd2b467cdc74f9d1ab8.png" width="249"></p> <p>0，3，2组成了微服务群组（环）a，他的 L 值为3，</p> <p>对于 a 来说，只有编号为 1 的 1 个微服务可以访问到 a，</p> <p>因此 a 的内聚值 H 为1</p> <p>答案输出微服务群组为0 3 2</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">12<br> 2 6 10 1 6 0 3 0 5 4 5 8</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">0&nbsp;2&nbsp;10&nbsp;5</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p><img alt="" height="371" src="https://img-blog.csdnimg.cn/direct/cf29d48d17f548548bfdd33c60e429d8.png" width="526"></p> 
    <ul> 
     <li> <p>1，6，3组成了微服务群组 (环) a1，L1值为3，编号为4、9的 2 个微服务可以访问到a1，因此V1值为2，H1为L1-V1 =1;</p> </li> 
     <li> <p>0，2，10，5组成了微服务群组 (环) a2，L2值为4，编号为7、8、11的3个微服务可以访问到a2，因此V2值为3，H2为L2-V2=1；</p> </li> 
     <li> <p>先对比H值，H1=H2，H值相等；</p> </li> 
     <li> <p>再对比环中序号最大值，a1中最大数为6，a2中最大数为10，a2排前面</p> </li> 
     <li> <p>因此输出答案为：0 2 10 5</p> </li> 
    </ul></td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

本题的edges数组记录了每个点 i 的直接下游点 edges\[i\]，其中 i 是数组索引，edges\[i\] 是数组元素值，二者一 一对应，因此每个节点其实只有一个直接下游节点（可以有多个直接上游节点），

如下图这种情况1->0, 1->2不会出现，因为edges\[1\]元素只能记录一个值。

![b5c61f98625144dba96af7f3ed8b7b4b.png][]

如下图情况是存在的 1->6，4->6，即一个节点可以有多个直接上游节点。

![428878de7eae4d9cadb9355816689ade.png][]

判断图中是否有环，主要有两种策略：

*  拓扑排序
 *  DFS/BFS

本题不仅需要我们判断是否有环，而且需要找出

*  环路点（下图红色圈点，即一个微服务群组的所有微服务数量为 L）
 *  （直接/间接）指向环路，但是不在环路的点（下图绿色圈点，即能够访问到该微服务群组的微服务数量为 V）

![5c86dd6b650e4b9fb3f34d9d8122fb1b.png][]

本题的主要难点在于，如何计算V值（能够访问到该微服务群组的微服务数量）。

我的思路如下，

首先利用拓扑排序，不停剥离入度为0的点，最后保留下来的点都是入度不为0的点，即环路点

> 关于拓扑排序剥离入度0的逻辑请看：[LeetCode - 207 课程表（Java & JS & Python & C）\_leetcode 课程-CSDN博客][LeetCode - 207 _Java _ JS _ Python _ C_leetcode _-CSDN]

可以发现，拓扑排序会把非环路的点都剥离掉，

因此，我们可以在剥离过程中，不断记录这些非环路的、被剥离的点数量，

我们可以定义一个数组preCount，长度为n，其中preCount\[i\]表示节点 i 的**直接或间接的**上游中的非环路的点的数量。

初始时：

*  计算各个点 i 的入度inDegree\[i\]，如下图红色数字
 *  初始化各个点 i 的preCount\[i\] = 0，如下图绿色数字

![c39acdf8929a4d9fbd978ce349502f30.png][]

假设节点 i 的下游节点为 j ，则 j = edges\[i\]，当我们剥离入度为0的点 i 时：

*  inDegree\[j\] -= 1
 *  preCount\[j\] = 1 + preCount\[i\]，含义是：节点 j 的上游节点数量 == （i 节点本身1个）+（i 的所有上游节点preCount\[i\]）

![388a9d795e454b75bf927589c8eda144.png][]

继续剥离入度为0的点：

![e6cb507bc43244f588376faa0b07c5cd.png][]

最后没有入度为0的点了，此时剩余点（inDegree\[i\] != 0的点）就是环路点，我们统计环路点 i 的 preCount\[i\] 之和，即为V值（能够访问到该微服务群组的微服务数量）。

本题要求我们选择环路中最小数作为环路起点，因此我们可以从0遍历到n-1，尝试作为环路起点start

*  如果 inDegree\[start\] == 0，则不能作为环路起点

然后定义 next = edges\[start\]，此时next即为start的下一个节点，若next != start，则说明环路还在探索中，此时继续 next = edges\[next\]，不停探索，直到 next == start 时，完成闭环。

> 上面解法有一个问题，那就是，我们遍历0到n-1每个点作为环路起点进行尝试，比如存在环路 0->2->10->5，
> 
> ![f55c3a0e2fd04edc9fe2a494cbe0c3c6.png][]
> 
> 我们一开始遍历到0作为起点开始尝试，发现可以找到该环路。
> 
> 之后遍历到2作为起点开始尝试，发现也可以找到该环路。
> 
> ....
> 
> 可以发现，将环路中任意一点作为起点，都可以探索出环路。那么就会有一个问题，同一个环路被探索了多次。
> 
> 如何避免这种冗余探索呢？
> 
> 我们可以定义一个长度为 n 的visited数组，visited\[i\] 表示 节点 i 是否被环路探索过，当我们遍历0作为起点探索时，每探索到一个环路点 i，则将 visited\[i\] = true。这样环路探索完，则环路中点的都被设置为visited=true的状态了。
> 
> 后续遍历到节点2作为起点时，首先检查其visited状态，如果为true，则可以放弃探索，因为他已经被探索过了。

#### JS算法源码 ####

#### Java算法源码 ####

import java.util.*;
    
    public class Main {
        static int n;
        static int[] edges;
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
    
            n = Integer.parseInt(sc.nextLine());
            edges = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    
            System.out.println(solution());
        }
    
        public static String solution() {
            // 统计各个点的入度
            int[] inDegree = new int[n];
            for (int i = 0; i < n; i++) {
                inDegree[edges[i]]++;
            }
    
            // 初始时，将入度为0的点入队
            LinkedList<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                if (inDegree[i] == 0) {
                    queue.addLast(i);
                }
            }
    
            // preCount[i]记录的是 i 点的所有（直接、间接）前驱点数量，因为这里是基于入度为0的点统计的，所以preCount[i]的点数量不含环内点的（环内点入度不可能为0）
            int[] preCount = new int[n];
            while (!queue.isEmpty()) {
                int i = queue.removeFirst();
    
                int j = edges[i];
                // j 的非环前驱点数量 = （间接前驱点数量preCount[i]个，即i的前驱点数量） + (直接前驱点数量1个，即i本身)
                preCount[j] = preCount[i] + 1;
    
                // 剥离入度0点
                if (--inDegree[j] == 0) {
                    queue.addLast(j);
                }
            }
    
            // 找环
            // max_h是题解要求的环的H值, 由于可能出现L<V的情况，所以max_h初始设为极小
            int max_h = Integer.MIN_VALUE;
            // max_p是题解要求的环的环中最大数
            int max_p = -1;
            // ans_path是题解要求的环的路径
            String ans_path = "";
    
            // visited[i]为true，表示i点是已被环路探索过
            boolean[] visited = new boolean[n];
            // 题目要求环路的起始编号为环中最小的数，因此我们从0遍历到n-1，依次作为环路起点开始探索
            for (int start = 0; start < n; start++) {
                // 环路点的入度不可能为0
                if (inDegree[start] == 0) continue;
    
                // 若start点已被环路探索过，则不可能是环路起点
                if (visited[start]) continue;
    
                // 否则start可以作为环路起点，并标记为访问过
                visited[start] = true;
    
                // 该环路的L值
                int l = 1;
                // 该环路的V值
                int v = preCount[start];
    
                // 记录环路路径
                StringJoiner path = new StringJoiner(" ");
                path.add(start + "");
    
                // p用于记录环路中最大数
                int p = start;
    
                // 环路探索
                int next = edges[start];
                // 如果next已被访问过，则环路探索回到起点，终止探索
                while (!visited[next]) {
                    // 否则标记next为已被探索过
                    visited[next] = true;
    
                    l++;
                    v += preCount[next];
                    p = Math.max(p, next);
                    path.add(next + "");
    
                    next = edges[next];
                }
    
                int h = l - v;
    
                // 按照内聚值 H 的结果从大到小的顺序对所有微服务群组（H 相等时，取环中最大的数进行比较）排序
                if (h > max_h || (h == max_h && p > max_p)) {
                    max_h = h;
                    max_p = p;
                    ans_path = path.toString();
                }
            }
    
            return ans_path;
        }
    }

#### Python算法源码 ####

import sys
    
    # 输入获取
    n = int(input())
    edges = list(map(int, input().split()))
    
    
    # 核心代码
    def solution():
        # 统计各个点的入度
        inDegree = [0] * n
    
        for i in range(n):
            inDegree[edges[i]] += 1
    
        # 初始时，将入度为0的点入队
        queue = []
        for i in range(n):
            if inDegree[i] == 0:
                queue.append(i)
    
        # preCount[i]记录的是 i 点的所有（直接、间接）前驱点数量，因为这里是基于入度为0的点统计的，所以preCount[i]的点数量不含环内点的（环内点入度不可能为0）
        preCount = [0] * n
        while len(queue) > 0:
            i = queue.pop(0)
            j = edges[i]
    
            # j 的非环前驱点数量 = （间接前驱点数量preCount[i]个，即i的前驱点数量） + (直接前驱点数量1个，即i本身)
            preCount[j] = preCount[i] + 1
    
            # 剥离入度0点
            inDegree[j] -= 1
            if inDegree[j] == 0:
                queue.append(j)
    
        # 找环
        max_h = -sys.maxsize  # max_h是题解要求的环的H值, 由于可能出现L<V的情况，所以max_h初始设为极小
        max_p = -1  # max_p是题解要求的环的环中最大数
        ans_path = []  # ans_path是题解要求的环的路径
    
        # visited[i]为true，表示i点是已被环路探索过
        visited = [False] * n
    
        # 题目要求环路的起始编号为环中最小的数，因此我们从0遍历到n-1，依次作为环路起点开始探索
        for start in range(n):
            # 环路点的入度不可能为0
            if inDegree[start] == 0:
                continue
    
            # 若start点已被环路探索过，则不可能是环路起点
            if visited[start]:
                continue
    
            # 否则start可以作为环路起点，并标记为访问过
            visited[start] = True
    
            # 该环路的L值
            L = 1
            # 该环路的V值
            V = preCount[start]
            # 记录环路路径
            path = [start]
            # p用于记录环路中最大数
            p = start
    
            # 环路探索
            next = edges[start]
            # 如果next已被访问过，则环路探索回到起点，终止探索
            while not visited[next]:
                # 否则标记next为已被探索过
                visited[next] = True
    
                L += 1
                V += preCount[next]
                p = max(p, next)
                path.append(next)
    
                next = edges[next]
    
            H = L - V
    
            # 按照内聚值 H 的结果从大到小的顺序对所有微服务群组（H 相等时，取环中最大的数进行比较）排序
            if H > max_h or (H == max_h and p > max_p):
                max_h = H
                max_p = p
                ans_path = path
    
        return " ".join(map(str, ans_path))
    
    
    # 输出打印
    print(solution())

#### C算法源码 ####

#include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <limits.h>
    
    /** 基于链表实现队列 **/
    typedef struct ListNode {
        int ele;
        struct ListNode *next;
    } ListNode;
    
    typedef struct LinkedList {
        int size;
        ListNode *head;
        ListNode *tail;
    } LinkedList;
    
    LinkedList *new_LinkedList() {
        LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
        link->size = 0;
        link->head = NULL;
        link->tail = NULL;
        return link;
    }
    
    void addLast_LinkedList(LinkedList *link, int ele) {
        ListNode *node = (ListNode *) malloc(sizeof(ListNode));
        node->ele = ele;
        node->next = NULL;
    
        if (link->size == 0) {
            link->head = node;
            link->tail = node;
        } else {
            link->tail->next = node;
            link->tail = node;
        }
    
        link->size++;
    }
    
    int removeFirst_LinkedList(LinkedList *link) {
        if (link->size == 0) exit(-1);
    
        ListNode *removed = link->head;
    
        if (link->size == 1) {
            link->head = NULL;
            link->tail = NULL;
        } else {
            link->head = link->head->next;
        }
    
        link->size--;
    
        return removed->ele;
    }
    
    // 全局变量
    int n;
    int *edges;
    
    // 核心代码
    void solution() {
        // 统计各个点的入度
        int *inDegree = (int *) calloc(n, sizeof(int));
        for (int i = 0; i < n; i++) {
            inDegree[edges[i]]++;
        }
    
        // 初始时，将入度为0的点入队
        LinkedList *queue = new_LinkedList();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                addLast_LinkedList(queue, i);
            }
        }
    
        // preCount[i]记录的是 i 点的所有（直接、间接）前驱点数量，因为这里是基于入度为0的点统计的，所以preCount[i]的点数量不含环内点的（环内点入度不可能为0）
        int *preCount = (int *) calloc(n, sizeof(int));
        while (queue->size > 0) {
            int i = removeFirst_LinkedList(queue);
            int j = edges[i];
    
            // j 的非环前驱点数量 = （间接前驱点数量preCount[i]个，即i的前驱点数量） + (直接前驱点数量1个，即i本身)
            preCount[j] = preCount[i] + 1;
    
            // 剥离入度0点
            if (--inDegree[j] == 0) {
                addLast_LinkedList(queue, j);
            }
        }
    
        // 找环
        // max_h是题解要求的环的H值, 由于可能出现L<V的情况，所以max_h初始设为极小
        int max_h = INT_MIN;
        // max_p是题解要求的环的环中最大数
        int max_p = -1;
        // ans_path是题解要求的环的路径
        LinkedList *ans_path;
    
        // visited[i]为true，表示i点是已被环路探索过
        int *visited = (int *) calloc(n, sizeof(int));
        // 题目要求环路的起始编号为环中最小的数，因此我们从0遍历到n-1，依次作为环路起点开始探索
        for (int start = 0; start < n; start++) {
            // 环路点的入度不可能为0
            if (inDegree[start] == 0) continue;
    
            // 若start点已被环路探索过，则不可能是环路起点
            if (visited[start]) continue;
    
            // 否则start可以作为环路起点，并标记为访问过
            visited[start] = 1;
    
            // 该环路的L值
            int L = 1;
            // 该环路的V值
            int V = preCount[start];
    
            // 记录环路路径
            LinkedList *path = new_LinkedList();
            addLast_LinkedList(path, start);
    
            // p用于记录环路中最大数
            int p = start;
    
            // 环路探索
            int next = edges[start];
            // 如果next已被访问过，则环路探索回到起点，终止探索
            while (!visited[next]) {
                // 否则标记next为已被探索过
                visited[next] = 1;
    
                L++;
                V += preCount[next];
                p = (int) fmax(p, next);
                addLast_LinkedList(path, next);
    
                next = edges[next];
            }
    
            int h = L - V;
    
            // 按照内聚值 H 的结果从大到小的顺序对所有微服务群组（H 相等时，取环中最大的数进行比较）排序
            if (h > max_h || (h == max_h && p > max_p)) {
                max_h = h;
                max_p = p;
                ans_path = path;
            }
        }
    
        // 打印结果
        ListNode *cur = ans_path->head;
        while (cur != NULL) {
            printf("%d ", cur->ele);
            cur = cur->next;
        }
    }
    
    int main() {
        scanf("%d", &n);
    
        edges = (int *) malloc(sizeof(int) * n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &edges[i]);
        }
    
        solution();
    
        return 0;
    }

#### C++算法源码 ####

#include <bits/stdc++.h>
    using namespace std;
    
    // 全局变量
    int n;
    vector<int> edges;
    
    // 核心代码
    void solution() {
        // 统计各个点的入度
        vector<int> inDegree(n, 0);
        for (int i = 0; i < n; i++) {
            inDegree[edges[i]]++;
        }
    
        // 初始时，将入度为0的点入队
        deque<int> que;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                que.push_back(i);
            }
        }
    
        // preCount[i]记录的是 i 点的所有（直接、间接）前驱点数量，因为这里是基于入度为0的点统计的，所以preCount[i]的点数量不含环内点的（环内点入度不可能为0）
        vector<int> preCount(n, 0);
        while (!que.empty()) {
            int i = que.front();
            que.pop_front();
    
            int j = edges[i];
    
            // j 的非环前驱点数量 = （间接前驱点数量preCount[i]个，即i的前驱点数量） + (直接前驱点数量1个，即i本身)
            preCount[j] = preCount[i] + 1;
    
            // 剥离入度0点
            if (--inDegree[j] == 0) {
                que.push_back(j);
            }
        }
    
        // 找环
        // max_h是题解要求的环的H值, 由于可能出现L<V的情况，所以max_h初始设为极小
        int max_h = INT_MIN;
        // max_p是题解要求的环的环中最大数
        int max_p = -1;
        // ans_path是题解要求的环的路径
        vector<int> ans_path;
    
        // visited[i]为true，表示i点是已被环路探索过
        vector<bool> visited(n, false);
        // 题目要求环路的起始编号为环中最小的数，因此我们从0遍历到n-1，依次作为环路起点开始探索
        for (int start = 0; start < n; start++) {
            // 环路点的入度不可能为0
            if (inDegree[start] == 0) continue;
    
            // 若start点已被环路探索过，则不可能是环路起点
            if (visited[start]) continue;
    
            // 否则start可以作为环路起点，并标记为访问过
            visited[start] = true;
    
            // 该环路的L值
            int L = 1;
            // 该环路的V值
            int V = preCount[start];
    
            // 记录环路路径
            vector<int> path(1, start);
    
            // p用于记录环路中最大数
            int p = start;
    
            // 环路探索
            int next = edges[start];
            // 如果next已被访问过，则环路探索回到起点，终止探索
            while (!visited[next]) {
                // 否则标记next为已被探索过
                visited[next] = true;
    
                L++;
                V += preCount[next];
                p = max(p, next);
                path.emplace_back(next);
    
                next = edges[next];
            }
    
            int h = L - V;
    
            // 按照内聚值 H 的结果从大到小的顺序对所有微服务群组（H 相等时，取环中最大的数进行比较）排序
            if (h > max_h || (h == max_h && p > max_p)) {
                max_h = h;
                max_p = p;
                ans_path = path;
            }
        }
    
        for (const auto &item: ans_path) {
            cout << item << " ";
        }
    }
    
    // 输入获取
    int main() {
        cin >> n;
    
        edges = vector<int>(n);
        for (int i = 0; i < n; i++) {
            cin >> edges[i];
        }
    
        // 算法调用
        solution();
    
        return 0;
    }

[- _ - HydroOJ]: https://hydro.ac/d/HWOCR/p/OCR037
[b5c61f98625144dba96af7f3ed8b7b4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/fc40532b562f49348d50ada926127996.png
[428878de7eae4d9cadb9355816689ade.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/aaa1780471ed4cacaa95dfa88a2fe760.png
[5c86dd6b650e4b9fb3f34d9d8122fb1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/a7db51ba8b184e1395311a45bdffc1ab.png
[LeetCode - 207 _Java _ JS _ Python _ C_leetcode _-CSDN]: https://fcqian.blog.csdn.net/article/details/127804547
[c39acdf8929a4d9fbd978ce349502f30.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/bbc3cda080ff4d048621421efe321535.png
[388a9d795e454b75bf927589c8eda144.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/ca99e8b8d9c448899bf93300016445f2.png
[e6cb507bc43244f588376faa0b07c5cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/2c401a79bc884ac5a8b5a9a01a015932.png
[f55c3a0e2fd04edc9fe2a494cbe0c3c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/1ff153556e704af497d48b836347f7d8.png