华为OD机试 - 服务失效判断 - 逻辑分析（Java 2023 B卷 200分）

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某系统中有众多服务，每个服务用字符串(只包含字母和数字，长度<=10)唯一标识，服务间可能有依赖关系，如A依赖B，则当B故障时导致A也故障。依赖具有传递性，如A依赖B，B依赖C，当C故障时导致B故障，也导致A故障。给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。

依赖关系：服务1-服务2表示“服务1”依赖“服务2”

不必考虑输入异常，用例保证:依赖关系列表、故障列表非空，且依赖关系数，故障服务数都不会超过3000服务标识格式正常。

二、输入描述

半角逗号分隔的依赖关系列表(换行)。

半角逗号分隔的故障服务列表。

三、输出描述

依赖关系列表中提及的所有服务中可以正常工作的服务列表，用半角逗号分隔，按依赖

关系列表中出现的次序排序。

特别的，没有正常节点输出单独一个半角逗号。

例如：

1、输入

a1-a2,a5-a6,a2-a3
a5,a2

2、输出

a6,a3

3、说明

• 所有服务+最先出现的序号：{a1=0, a2=1, a3=5, a5=2, a6=3}
• 故障的服务：[a1, a2, a5]
• 正常的服务+最先出现的序号：{a3=5, a6=3}
• 输出a6,a3

四、解题思路

1. 输入依赖关系列表；
2. 输入故障服务列表；
3. 定义dependenceMap，存储依赖关系，key：故障服务，value：被关联的服务；
4. 定义serviceMap，存储所有服务，key：服务，value：服务出现的次序；
5. 定义badSet，存储所有故障服务；
6. 通过while语句，获取所有故障服务；
7. 遍历badSet，从所有服务中移除故障服务；
8. 如果没有正常节点，输出单独一个半角逗号；
9. 按依赖关系列表中出现的次序排序，输出正常的点。

五、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] arr = sc.nextLine().split(",");// 故障服务列表String[] badArr = sc.nextLine().split(",");// key：故障服务，value：被关联的服务Map<String, String> dependenceMap = new HashMap<>();// 所有服务 key：服务，value：服务出现的次序Map<String, Integer> serviceMap = new HashMap<>();int idx = 0;for (String service : arr) {String[] temp = service.split("-");dependenceMap.put(temp[1], temp[0]);serviceMap.putIfAbsent(temp[0], idx++);serviceMap.putIfAbsent(temp[1], idx++);}Set<String> badSet = new HashSet<>();for (int i = 0; i < badArr.length; i++) {String bad = badArr[i];badSet.add(bad);// 获取所有故障服务while (dependenceMap.containsKey(bad)) {bad = dependenceMap.get(bad);badSet.add(bad);}}System.out.println("所有服务+最先出现的序号：" + serviceMap);System.out.println("故障的服务：" + badSet);// 正常的服务 = 所有服务 - 故障的服务badSet.forEach(x -> serviceMap.remove(x));System.out.println("正常的服务+最先出现的序号：" + serviceMap);// 没有正常节点输出单独一个半角逗号if(serviceMap.size()==0){System.out.println(",");return;}// 按依赖关系列表中出现的次序排序输出正常的点StringJoiner stringJoiner = new StringJoiner(",");new ArrayList<>(serviceMap.entrySet()).stream().sorted(Comparator.comparingInt(Map.Entry::getValue)).forEach(x -> stringJoiner.add(x.getKey()));System.out.println(stringJoiner);
}

六、效果展示

1、输入

a10-a1,a5-a6,a2-a3,a6-a1,a4-a3,a3-a5
a5,a2

2、输出

a10,a1,a6

3、说明

• 所有服务+最先出现的序号：{a1=1, a10=0, a2=4, a3=5, a4=8, a5=2, a6=3}
• 故障的服务：[a2, a3, a4, a5]
• 正常的服务+最先出现的序号：{a1=1, a10=0, a6=3}
• 按序号输出正常的服务a10,a1,a6

🏆下一篇：华为OD机试 - 荒岛求生 - 栈Stack（Java 2023 B卷 100分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。