华为机试题:计算链路长度

题目描述

在数据链路中,每个设备都有数据流入设备和流出设备,流入流出关系通过一个表格记录,请根据给出的记录表,计算出设备所属链路的最大长度(链路的节点个数)

输入描述:

第1行输入为关系记录的数量 N, N<=100
第2行输入为待计算所属链路的最大长度的设备0
从第3至N+2行输入为关系记录,每一行关系记录按照设备ID,流入设备ID,流出设备ID空格字符分隔。每个设备都有自己的关系记录

输出描述:

对于每组测试数据,输出0所属链路的最大长度

用例1

输入:

4
device1
device1 device2 device3
device2 null device1
device3 device1 device4
device4 device3 null

输出:

4

用例说明:

第一行数据4表示有4条数据关系记录。
第二行数据device1表示需要计算device1的所属链路的最长长度。
第三行device1 device2 device3:设备device1的流入设备有 device2,流出设备有deviec3。
第四行device2 null device1:设备device2没有流入设备,流出设备有device1。
第五行device3 device1 device4:设备device3的流入设备有 device1,流出设备有device4。
第六行device4 device3 null:设备device4的流入设备有device3,没有流出设备。

根据上述信息可以还原出一条链路关系:device2->device1->device3->device4
注:当没有流入设备或者流出设备时,用 null 字符表示。

用例2:

输入:

8
d3
d1 null d2
d2 d1 d3
d2 d1 d5
d2 d1 d4
d3 d2 null
d4 d2 null
d5 d2 d6
d8 d5 null

输出:

3

备注:

一个设备可以属于多个链路,每个设备只有一个流入设备,但每个设备可以有多个流出设备,切各设备组成的链路不存在环路。

解题代码:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = Integer.parseInt(scanner.nextLine());
        String deviceId = scanner.nextLine();
        String root = null;
        // 键为设备ID,值为流入设备
        Map<String, String> registry = new HashMap<>();
        for (int i = 0; i < size; i++) {
            String line = scanner.nextLine();
            String[] record = line.split(" ");
            if ("null".equals(record[1])) {
                root = record[0];
                registry.put(root, null);
            } else {
                registry.put(record[0], record[1]);
            }
            // 终点设备
            if (!"null".equals(record[2])) {
                registry.put(record[2], record[0]);
            }
        }

        Map<String, Integer> maxPathMap = maxPath(registry);
        System.out.println(maxPathMap.get(deviceId));
    }

    public static Map<String, Integer> maxPath(Map<String, String> path) {
        Map<String, Integer> result = new HashMap<>();
        Set<String> devices = path.keySet();
        for (String d : devices) {
            // 表示路径长度
            int length = 1;
            String front = d;
            Set<String> deviceInPath = new HashSet<>();
            deviceInPath.add(d);
            for(;;) {
                front = path.get(front);
                if (front == null) {
                    break;
                }
                deviceInPath.add(front);
                length++;
            }
            // 更新路径中所有节点的最大路径
            Integer max;
            for (String s : deviceInPath) {
                max = result.getOrDefault(s, length);
                max = Math.max(max, length);
                result.put(s, max);
            }
        }
        return result;
    }

}

自编用例:

输入:

1
d1
d1 null null

输出

1
上一篇:Kafka 如果丢了消息,怎么处理的?


下一篇:leetcode 530. 二叉搜索树的最小绝对差(Java版)