最新华为OD机试真题-启动多任务排序(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 启动多任务排序(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

启动多任务排序

问题描述

卢小姐在开发一个应用程序，启动时需要执行多个初始化任务。这些任务之间可能存在依赖关系，例如任务 依赖任务 ，那么必须在任务 执行完成之后，才能开始执行任务 。现在给出多条任务依赖关系的规则，请输出任务的执行顺序。规则采用贪心策略，即如果一个任务没有依赖的任务，则立即开始执行；如果同时有多个任务可以执行，则按照任务名称的字母顺序排序。

例如，如果任务 依赖任务 ，任务 依赖任务 ，任务 依赖任务 和任务 ，同时任务 还依赖任务 ，那么执行任务的顺序应该是：任务 、任务 、任务 、任务 、任务 。这里任务 和任务 都是没有依赖的，可以立即执行。

输入格式

输入由若干个任务依赖规则组成，每个规则表示两个任务之间的依赖关系。规则使用符号 -> 表示依赖方向，例如 A->B 表示任务 依赖任务 。多个依赖规则之间用单个空格分隔。

输出格式

输出为排序后的启动任务列表，多个任务之间用单个空格分隔。

样例输入

A->B C->B

样例输出

B A C

数据范围

任务名称为大写字母 到 ，输入数据保证任务依赖关系合法且无循环依赖。

题解

本题可以使用拓扑排序来解决。首先，根据输入的任务依赖规则，构建任务之间的有向图。然后，统计每个任务的入度（即有多少个任务依赖当前任务）。

接下来，将所有入度为 的任务加入队列，表示这些任务可以立即执行。每次从队列中取出一个任务，将其加入结果列表，并将该任务指向的所有任务的入度减 。如果减 后某个任务的入度变为 ，则将其加入队列。

重复上述过程，直到队列为空。最后，按照结果列表中任务的顺序输出即可。

如果同时有多个任务可以执行，则按照任务名称的字母顺序排序后再加入结果列表。

时间复杂度为 ，其中 为任务数量， 为任务依赖关系数量。空间复杂度为 。

参考代码

• Python

from collections import deque

def main():
    rules = input().split()
    n = len(rules)
    in_degree = [0] * 26
    graph = [[] for _ in range(26)]
    vis = [False] * 26

    for rule in rules:
        a = ord(rule[0]) - ord('A')
        b = ord(rule[3]) - ord('A')
        in_degree[a] += 1
        graph[b].append(a)
        vis[a] = vis[b] = True

    q = deque()
    res = []
    tmp = []

    for i in range(26):
        if in_degree[i] == 0 and vis[i]:
            q.append(i)
            tmp.append(i)

    while q:
        tmp.sort()
        res.extend(tmp)
        tmp.clear()

        for _ in range(len(q)):
            task = q.popleft()
            for nxt in graph[task]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    q.append(nxt)
                    tmp.append(nxt)

    print(' '.join(chr(x + ord('A')) for x in res))

if __name__ == '__main__':
    main()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] rules = in.nextLine().split(" ");
        int n = rules.length;
        int[] inDegree = new int[26];
        boolean[] vis = new boolean[26];

        List<Integer>[] graph = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            graph[i] = new ArrayList<>();
        }

        for (String rule : rules) {
            int a = rule.charAt(0) - 'A';
            int b = rule.charAt(3) - 'A';
            inDegree[a]++;
            graph[b].add(a);
            vis[a] = vis[b] = true;
        }

        Deque<Integer> q = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();

        for (int i = 0; i < 26; i++) {
            if (inDegree[i] == 0 && vis[i]) {
                q.add(i);
                tmp.add(i);
            }
        }

        while (!q.isEmpty()) {
            Collections.sort(tmp);
            res.addAll(tmp);
            tmp.clear();

            for (int sz = q.size(); sz > 0; sz--) {
                int task = q.poll();
                for (int nxt : graph[task]) {
                    inDegree[nxt]--;
                    if (inDegree[nxt] == 0) {
                        q.add(nxt);
                        tmp.add(nxt);
                    }
                }
            }
        }

        for (int x : res) {
            char c = (char) (x + 'A');
            System.out.print(c + " ");
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    vector<string> rules;
    int pos = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') {
            rules.push_back(s.substr(pos, i - pos));
            pos = i + 1;
        }
    }
    rules.push_back(s.substr(pos));

    int n = rules.size();
    vector<int> inDegree(26, 0);
    vector<bool> vis(26, false);
    vector<vector<int>> graph(26);

    for (auto rule : rules) {
        int a = rule[0] - 'A';
        int b = rule[3] - 'A';
        inDegree[a]++;
        graph[b].push_back(a);
        vis[a] = vis[b] = true;
    }

    queue<int> q;
    vector<int> res;
    vector<int> tmp;

    for (int i = 0; i < 26; i++) {
        if (inDegree[i] == 0 && vis[i]) {
            q.push(i);
            tmp.push_back(i);
        }
    }

    while (!q.empty()) {
        sort(tmp.begin(), tmp.end());
        res.insert(res.end(), tmp.begin(), tmp.end());
        tmp.clear();

        for (int sz = q.size(); sz > 0; sz--) {
            int task = q.front();
            q.pop();
            for (int nxt : graph[task]) {
                inDegree[nxt]--;
                if (inDegree[nxt] == 0) {
                    q.push(nxt);
                    tmp.push_back(nxt);
                }
            }
        }
    }

    for (int x : res) {
        char c = x + 'A';
        cout << c << " ";
    }

    return 0;
}