【华为OD-E卷 -52 服务失效判断 100分（python、java、c++、js、c）】

25-03-07 19:22

3960

11541

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 服务失效判断 100分（python、java、c++、js、c）】

题目

某系统中有众多服务，每个服务用字符串（只包含字母和数字，长度<=10）唯一标识，服务间可能有依赖关系，如A依赖B，则当B故障时导致A也故障。
依赖具有传递性，如A依赖B，B依赖C，当C故障时导致B故障，也导致A故障。
给出所有依赖关系，以及当前已知故障服务，要求输出所有正常服务。
依赖关系：服务1-服务2 表示“服务1”依赖“服务2”
不必考虑输入异常，用例保证：依赖关系列表、故障列表非空，且依赖关系数，故障服务数都不会超过3000，服务标识格式正常。

输入描述

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

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

输出描述

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

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

用例

用例一：

输入：

a1-a2,a5-a6,a2-a3
a5,a2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

a6,a3
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

a1-a2
a2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2

输出：

,
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

python解法

解题思路：
输入处理:

将服务和依赖关系解析为dependencies列表，格式为 [[“服务1”, “依赖服务”], …]。
将故障服务解析为faults集合。
构建依赖图:

使用dep_graph字典表示服务之间的依赖关系，键是被依赖的服务，值是依赖该服务的服务集合。
使用order字典记录每个服务出现的顺序，方便最终输出时排序。
故障传播模拟:

从faults集合中的服务开始，将它们加入队列queue。
遍历队列，移除当前服务，并找到依赖该服务的所有服务，将它们标记为故障，并加入队列。
筛选未受影响的服务:

遍历所有服务，排除已标记为故障的服务，剩下的服务即为仍然可用的服务。
按输入顺序输出:

对剩下的服务按照order字典的顺序排序并输出

# 输入格式：依赖关系（"服务-依赖服务,服务-依赖服务"）
dependencies = [pair.split("-") for pair in input().split(",")]
# 输入格式：故障服务（"服务,服务"）
faults = set(input().split(","))

def find_services():
    # 依赖图：记录每个服务被哪些服务依赖
    dep_graph = {}
    # 记录服务的输入顺序，用于排序
    order = {}

    index = 0  # 顺序索引
    # 构建依赖图和顺序字典
    for dep, required in dependencies:
        # 初始化被依赖服务的依赖图条目
        if required not in dep_graph:
            dep_graph[required] = set()
        dep_graph[required].add(dep)  # 添加依赖关系

        # 初始化依赖服务的依赖图条目（即使没有被依赖也要存在于图中）
        if dep not in dep_graph:
            dep_graph[dep] = set()

        # 记录服务的顺序
        if dep not in order:
            order[dep] = index
            index += 1
        if required not in order:
            order[required] = index
            index += 1

    # 初始化故障传播队列和已访问服务集合
    queue = list(faults)  # 队列记录待处理的故障服务
    visited = set(queue)  # 记录已标记为故障的服务

    # 模拟故障传播
    while queue:
        fault = queue.pop(0)  # 弹出当前故障服务
        if fault in dep_graph:
            # 找到所有依赖该服务的服务
            for dependent in dep_graph.pop(fault, []):
                # 如果依赖的服务尚未被标记为故障，则标记并加入队列
                if dependent not in visited:
                    queue.append(dependent)
                    visited.add(dependent)

    # 计算未受影响的服务（未被标记为故障的服务）
    active_services = [svc for svc in order if svc not in visited]

    # 如果所有服务都被故障影响，返回逗号
    if not active_services:
        return ","
    
    # 按服务的输入顺序排序并返回结果
    return ",".join(sorted(active_services, key=lambda x: order[x]))

# 输出结果
print(find_services())

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

解题思路
输入处理:

第一行输入依赖关系（格式如A-B,B-C），解析为依赖对列表rels。
第二行输入故障服务（格式如A,C），解析为故障服务列表fails。
构建依赖关系映射:

使用depMap记录服务之间的依赖关系，键是被依赖的服务，值是依赖该服务的服务集合。
使用orderMap记录服务的输入顺序，用于最终按顺序输出。
故障传播:

对于每个故障服务，使用栈遍历其依赖的所有服务，将受影响的服务标记为故障。
筛选未受影响的服务:

遍历所有服务，排除被标记为故障的服务，得到仍然可用的服务列表。
按输入顺序输出:

对剩下的可用服务列表，按照orderMap中记录的顺序排序并输出。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取第一行输入：依赖关系字符串，格式如"A-B,B-C"
        String relInput = sc.nextLine();
        List<String> relPairs = split(relInput, ',');

        // 将依赖关系解析为Pair对象的列表
        List<Pair<String, String>> rels = new ArrayList<>();
        for (String pStr : relPairs) {
            List<String> p = split(pStr, '-');
            rels.add(new Pair<>(p.get(0), p.get(1))); // p.get(0)为依赖服务，p.get(1)为被依赖服务
        }

        // 读取第二行输入：故障服务字符串，格式如"A,C"
        String failInput = sc.nextLine();
        List<String> fails = split(failInput, ',');

        // 输出结果
        System.out.println(getActive(rels, fails));
    }

    // 工具方法：将字符串按指定分隔符拆分为列表
    public static List<String> split(String s, char d) {
        return Arrays.asList(s.split(String.valueOf(d))); // 使用String的split方法分隔字符串
    }

    // 核心方法：根据依赖关系和故障服务，计算仍然可用的服务
    public static String getActive(List<Pair<String, String>> rels, List<String> fails) {
        // 依赖图：键为被依赖的服务，值为依赖该服务的服务集合
        Map<String, Set<String>> depMap = new HashMap<>();
        // 故障服务集合，用于快速判断服务是否故障
        Set<String> failSet = new HashSet<>(fails);
        // 服务的顺序映射，用于输出时排序
        Map<String, Integer> orderMap = new HashMap<>();

        // 构建依赖图和顺序映射
        int idx = 0;
        for (Pair<String, String> rel : rels) {
            String dep = rel.getKey();   // 依赖的服务
            String prov = rel.getValue(); // 被依赖的服务

            // 构建依赖图：被依赖服务prov对应依赖它的服务集合
            depMap.computeIfAbsent(prov, k -> new HashSet<>()).add(dep);

            // 记录服务的顺序（如果服务未出现过则记录）
            orderMap.putIfAbsent(dep, idx++);
            orderMap.putIfAbsent(prov, idx++);
        }

        // 模拟故障传播：从每个故障服务开始，标记所有受影响的服务
        for (String fail : fails) {
            Stack<String> stk = new Stack<>(); // 使用栈进行深度优先搜索
            stk.push(fail);

            while (!stk.isEmpty()) {
                String svc = stk.pop(); // 弹出当前服务

                // 如果当前服务有依赖服务，处理这些服务
                if (depMap.containsKey(svc)) {
                    for (String dep : depMap.get(svc)) {
                        // 如果依赖的服务未被标记为故障，则标记为故障并加入栈
                        if (!failSet.contains(dep)) {
                            failSet.add(dep);
                            stk.push(dep);
                        }
                    }
                    depMap.remove(svc); // 处理完当前服务后，从依赖图中移除
                }
            }
        }

        // 收集仍然可用的服务（不在故障集合中的服务）
        List<String> operList = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : orderMap.entrySet()) {
            if (!failSet.contains(entry.getKey())) {
                operList.add(entry.getKey());
            }
        }

        // 如果所有服务都不可用，返回逗号
        if (operList.isEmpty()) {
            return ",";
        }

        // 按服务的输入顺序排序
        operList.sort(Comparator.comparingInt(orderMap::get));

        // 将可用服务列表拼接为逗号分隔的字符串并返回
        return String.join(",", operList);
    }

    // 辅助类：表示依赖关系的键值对
    public static class Pair<K, V> {
        private final K key;   // 键：依赖服务
        private final V value; // 值：被依赖服务

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

解题思路
输入解析:

第一行输入描述服务之间的依赖关系（如 A-B,B-C），将其解析为relations列表，存储为键值对（dependent 和 provider）。
第二行输入故障服务列表（如 A,C），将其存储为字符串列表failures。
构建依赖图和服务顺序:

使用 dependencyMap 记录服务之间的依赖关系：
键是被依赖的服务，值是依赖该服务的服务集合。
使用 appearanceOrder 记录每个服务首次出现的顺序，用于最终结果排序。
模拟故障传播:

对于每个故障服务，使用栈（DFS）遍历其依赖的所有服务，标记为故障，并将它们加入栈中，直到没有更多服务受影响。
筛选可用服务:

遍历所有服务，排除已标记为故障的服务，剩余的服务即为仍然可用的服务。
按输入顺序输出:

对可用服务按照 appearanceOrder 的顺序排序，并用逗号拼接输出。如果没有可用服务，直接输出 ,。

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// 工具函数：将字符串按指定分隔符分割为子字符串列表
vector<string> split(const string& s, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(s);
    while (getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

// 核心函数：根据依赖关系和故障服务，计算仍然可用的服务
string determineActiveServices(const vector<pair<string, string>>& relations, const vector<string>& failures) {
    // 依赖图：被依赖服务 -> 依赖它的服务集合
    map<string, set<string>> dependencyMap;
    // 故障服务集合，用于快速判断服务是否故障
    set<string> failureSet(failures.begin(), failures.end());
    // 服务顺序映射：记录服务首次出现的顺序，用于最终排序
    map<string, int> appearanceOrder;
    
    int index = 0;
    // 构建依赖图和服务顺序映射
    for (const auto& relation : relations) {
        const string& dependent = relation.first;   // 依赖服务
        const string& provider = relation.second;  // 被依赖服务
        
        // 构建依赖图：被依赖服务指向依赖它的服务
        dependencyMap[provider].insert(dependent);

        // 记录服务的输入顺序
        if (appearanceOrder.find(dependent) == appearanceOrder.end()) {
            appearanceOrder[dependent] = index++;
        }
        if (appearanceOrder.find(provider) == appearanceOrder.end()) {
            appearanceOrder[provider] = index++;
        }
    }

    // 模拟故障传播
    for (const auto& failure : failures) {
        stack<string> stack; // 使用栈进行深度优先搜索（DFS）
        stack.push(failure);

        while (!stack.empty()) {
            string service = stack.top(); // 弹出栈顶服务
            stack.pop();

            // 如果当前服务有依赖服务，处理这些依赖服务
            if (dependencyMap.find(service) != dependencyMap.end()) {
                for (const auto& dependent : dependencyMap[service]) {
                    // 如果依赖服务尚未被标记为故障，则标记为故障并加入栈
                    if (failureSet.find(dependent) == failureSet.end()) {
                        failureSet.insert(dependent);
                        stack.push(dependent);
                    }
                }
                // 从依赖图中移除当前服务
                dependencyMap.erase(service);
            }
        }
    }

    // 筛选仍然可用的服务（不在故障集合中的服务）
    vector<string> operationalList;
    for (const auto& entry : appearanceOrder) {
        if (failureSet.find(entry.first) == failureSet.end()) {
            operationalList.push_back(entry.first);
        }
    }

    // 如果所有服务都不可用，返回逗号
    if (operationalList.empty()) {
        return ",";
    }

    // 按服务的输入顺序排序
    sort(operationalList.begin(), operationalList.end(), [&](const string& a, const string& b) {
        return appearanceOrder[a] < appearanceOrder[b];
    });

    // 将可用服务列表拼接为逗号分隔的字符串
    string result = operationalList[0];
    for (size_t i = 1; i < operationalList.size(); ++i) {
        result += "," + operationalList[i];
    }

    return result;
}

int main() {
    // 读取第一行输入：依赖关系字符串
    string relationsInput;
    getline(cin, relationsInput);
    vector<string> relationsPairs = split(relationsInput, ',');

    // 将依赖关系字符串解析为键值对列表
    vector<pair<string, string>> relations;
    for (const auto& pairStr : relationsPairs) {
        vector<string> pair = split(pairStr, '-');
        relations.emplace_back(pair[0], pair[1]);
    }

    // 读取第二行输入：故障服务字符串
    string failuresInput;
    getline(cin, failuresInput);
    vector<string> failures = split(failuresInput, ',');

    // 输出结果
    cout << determineActiveServices(relations, failures) << endl;

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

C解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

JS解法

解题思路
输入解析:

第一行输入表示依赖关系，格式如 A-B,B-C，解析为二维数组 rel，其中每个元素是 [依赖服务, 被依赖服务]。
第二行输入表示故障服务，格式如 A,C，解析为数组 brk。
构建依赖关系图和服务顺序:

使用 nxt 构建依赖关系图：
键是被依赖的服务，值是依赖它的服务集合。
使用 fst 记录每个服务的输入顺序，用于最终结果的排序。
故障传播:

遍历故障服务列表 brk，从每个故障服务开始，递归删除所有依赖它的服务，并从依赖关系图中移除。
筛选可用服务:

剩余在依赖关系图 nxt 中的服务即为未受影响的服务。
按 fst 中的顺序对这些服务进行排序。
返回结果:

如果没有可用服务，返回 ,。
否则，返回按顺序排序后，用逗号拼接的可用服务列表。

const readline = require("readline");

// 创建标准输入输出接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 存储输入的两行数据
const ln = [];
rl.on("line", (line) => {
    ln.push(line);

    // 当两行输入均已读取时处理
    if (ln.length === 2) {
        // 第一行解析为依赖关系数组
        const rel = ln[0].split(",").map((p) => p.split("-"));
        // 第二行解析为故障服务数组
        const brk = ln[1].split(",");

        // 计算未受影响的服务并输出
        console.log(getNorm(rel, brk));

        // 清空输入数组，准备下一组输入
        ln.length = 0;
    }
});

// 核心函数：根据依赖关系和故障服务，计算未受影响的服务
function getNorm(rel, brk) {
    // 依赖关系图：记录被依赖服务 -> 依赖它的服务集合
    const nxt = {};
    // 服务顺序：记录每个服务首次出现的顺序
    const fst = {};
    let idx = 0;

    // 构建依赖关系图和服务顺序
    for (let [c, f] of rel) {
        // 初始化依赖关系图条目
        if (!nxt[c]) nxt[c] = new Set();
        if (!nxt[f]) nxt[f] = new Set();
        // 被依赖服务 f 增加依赖它的服务 c
        nxt[f].add(c);

        // 记录服务的顺序
        if (!fst[c]) fst[c] = idx++;
        if (!fst[f]) fst[f] = idx++;
    }

    // 模拟故障传播：从每个故障服务开始，递归删除所有依赖它的服务
    for (let s of brk) {
        del(nxt, s);
    }

    // 收集剩余未受影响的服务
    const res = Object.keys(nxt);
    // 如果所有服务都受影响，返回 ","
    if (res.length == 0) return ",";
    // 按服务的输入顺序排序并返回结果
    return res.sort((a, b) => fst[a] - fst[b]).join(",");
}

// 辅助函数：递归删除所有受影响的服务
function del(nxt, s) {
    // 如果服务 s 存在于依赖关系图中
    if (nxt[s]) {
        // 获取所有依赖于服务 s 的服务集合
        const rm = nxt[s];
        // 从依赖关系图中移除服务 s
        delete nxt[s];

        // 对每个依赖于服务 s 的服务，递归删除
        for (let ss of rm) {
            del(nxt, ss);
        }
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145052246"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！