华为OD机试真题 Java 实现【快递投放问题】【2023 B卷 100分】，附详细解题思路

在这里插入图片描述

一、题目描述

有N个快递站点用字符串标识，某些站点之间有道路连接。每个站点有一些包裹要运输，每个站点间的包裹不重复，路上有检查站会导致部分货物无法通行，计算哪些货物无法正常投递。

二、输入描述

第一行输入M N，M个包裹N个道路信息。

0<=M，N<=100，检查站禁止通行的包裹如果有多个以空格分开。

三、输出描述

输出不能送达的包裹 package2 package4，如果所有包裹都可以送达则输出none，输出结果按照升序排列

四、Java算法源码

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    // M个包裹
    int M = sc.nextInt();
    // N个道路
    int N = sc.nextInt();
    sc.nextLine();

    /**
     * key：包裹名
     * value：运输路径
     */
    Map<String, String> mapOk = new HashMap<>();
    for (int i = 0; i < M; i++) {
        String[] strings = sc.nextLine().split(" ");
        mapOk.put(strings[0], strings[1] + strings[2]);
    }

    /**
     * key：路径名
     * value：被拦截的包裹名
     */
    Map<String, List<String>> mapNg = new HashMap<>();
    for (int i = 0; i < N; i++) {
        String[] strings = sc.nextLine().split(" ");
        List<String> noList = new ArrayList<>();
        for (int j = 2; j < strings.length; j++) {
            noList.add(strings[j]);
        }
        mapNg.put(strings[0] + strings[1], noList);
    }

    List<String> retList = new ArrayList<>();
    for (Map.Entry<String, List<String>> map : mapNg.entrySet()) {
        // 路径名
        String key = map.getKey();
        // 被拦截的包裹
        List<String> list = map.getValue();
        for (String s : list) {
            // 被拦截的包裹的运输路径等于此路径则表示包裹被拦截
            if (key.equals(mapOk.get(s))) {
                retList.add(s);
            }
        }
    }

    System.out.println(retList);
}