(新卷,200分)- 服务失效判断（Java JS Python）

(新卷,200分)- 服务失效判断（Java & JS & Python）

题目描述

某系统中有众多服务，每个服务用字符串（只包含字母和数字，长度<=10）唯一标识，服务间可能有依赖关系，如A依赖B，则当B故障时导致A也故障。

依赖具有传递性，如A依赖B，B依赖C，当C故障时导致B故障，也导致A故障。

给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。

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

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

输入描述

半角逗号分隔的依赖关系列表（换行）

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

输出描述

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

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

用例

题目解析

我的解题思路是：

根据第一行输入的依赖关系，统计出每个服务的直接子服务，记录在next中。

另外由于题目输出描述中说：输出的服务要按照：

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

因此，这里我还定义了一个first，用于记录每个服务第一次出现的位置。

当上面统计好后，就可以遍历第二行输入的故障服务列表了。

每遍历到一个故障服务，则删除next中对应服务，但是删除前，需要先记录将要删除服务的所有子服务。删除当前故障服务后，继续递归删除其子服务。

这样next剩下的就是正常服务了。

此时再按照first记录的出现位置对剩余的正常服务排序即可，

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { const relatons = lines[0].split(",").map((p) => p.split("-")); // 先决条件 const breakdowns = lines[1].split(","); // 故障机器 console.log(getNormalMachine(relatons, breakdowns)); lines.length = 0; } }); function getNormalMachine(relatons, breakdowns) { const next = {}; // 属性是父服务，属性值是子服务集合 const first = {}; // 记录服务第一次出现的位置 let i = 0; for (let [c, f] of relatons) { if (!next[c]) next[c] = new Set(); if (!next[f]) next[f] = new Set(); next[f].add(c); if (!first[c]) first[c] = i++; if (!first[f]) first[f] = i++; } for (let s of breakdowns) { remove(next, s); } const ans = Object.keys(next); if (ans.length == 0) return ","; return ans.sort((a, b) => first[a] - first[b]).join(","); } // 由于服务s是故障服务，因此s服务本身，和其所有子孙服务都无法运行 function remove(next, s) { if (next[s]) { const need_remove = next[s]; delete next[s]; for (let ss of need_remove) { remove(next, ss); } } }

Java算法源码

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[][] relations = Arrays.stream(sc.nextLine().split(",")).map(s -> s.split("-")).toArray(String[][]::new); String[] breakdowns = sc.nextLine().split(","); System.out.println(getResult(relations, breakdowns)); } public static String getResult(String[][] relations, String[] breakdowns) { HashMap<String, HashSet<String>> next = new HashMap<>(); // 属性是父服务，属性值是子服务集合 HashMap<String, Integer> first = new HashMap<>(); // 记录服务第一次出现的位置 int i = 0; for (String[] relation : relations) { String c = relation[0]; String f = relation[1]; next.putIfAbsent(c, new HashSet<>()); next.putIfAbsent(f, new HashSet<>()); next.get(f).add(c); first.putIfAbsent(c, i++); first.putIfAbsent(f, i++); } for (String s : breakdowns) { remove(next, s); } String[] ans = next.keySet().toArray(new String[0]); if (ans.length == 0) return ","; Arrays.sort(ans, (a, b) -> first.get(a) - first.get(b)); StringJoiner sj = new StringJoiner(","); for (String an : ans) sj.add(an); return sj.toString(); } // 由于服务s是故障服务，因此s服务本身，和其所有子孙服务都无法运行 public static void remove(HashMap<String, HashSet<String>> next, String s) { if (next.containsKey(s)) { HashSet<String> need_remove = next.get(s); next.remove(s); for (String ss : need_remove) { remove(next, ss); } } } }

Python算法源码

# 输入获取 relations = [s.split("-") for s in input().split(",")] breakdowns = input().split(",") def remove(next, s): if next.get(s) is not None: need_remove = next[s] del next[s] for ss in need_remove: remove(next, ss) # 算法入口 def getResult(): next = {} first = {} i = 0 for c, f in relations: if next.get(c) is None: next[c] = set() if next.get(f) is None: next[f] = set() next[f].add(c) if first.get(c) is None: first[c] = i i += 1 if first.get(f) is None: first[f] = i i += 1 for s in breakdowns: remove(next, s) ans = list(next.keys()) if len(ans) == 0: return "," ans.sort(key=lambda x: first[x]) return ",".join(ans) # 算法调用 print(getResult())