启动多任务排序 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
一个应用启动时,会有多个初始化任务需要执行,并且任务之间有依赖关系,例如A任务依赖B任务,那么必须在B任务执行完成之后,才能开始执行A任务。
现在给出多条任务依赖关系的规则,请输入任务的顺序执行序列,规则采用贪婪策略,即一个任务如果没有依赖的任务,则立刻开始执行,如果同时有多个任务要执行,则根据任务名称字母顺序排序。
例如: B任务依赖A任务,C任务依赖A任务,D任务依赖B任务和C任务,同时,D任务还依赖E任务。那么执行任务的顺序由先到后是:A任务,E任务,B任务,C任务,D任务。这里A和E任务都是没有依赖的,立即执行。
输入描述
输入参数每个元素都表示任意两个任务之间的依赖关系,输入参数中符号”->”表示依赖方向。
例如A->B表示A依赖B,多个依赖之间用单个空格分割
输出描述
输出为排序后的启动任务列表,多个任务之间用单个空格分割
示例1
输入:
A->B C->B
输出:
B A C
题解
这是一个典型的拓扑排序问题,通过建立任务之间的依赖关系图,然后按照一定规则执行任务,即先执行没有依赖的任务,然后再执行依赖于前面任务的任务。
以下是解题思路和代码大致描述:
- 使用两个字典,
outdegree
用于记录每个任务的出度(依赖它的任务数量),depend
用于记录每个任务依赖的任务列表。- 遍历输入的任务依赖关系,构建任务之间的依赖图,并同时维护出度信息。
- 利用拓扑排序的思想,循环执行以下步骤:
- 找到出度为0的任务,如果存在多个,按字母顺序排序。
- 将该任务加入结果集,并标记该任务已遍历。
- 更新邻居任务的出度,将它们的出度减1。
- 重复上述步骤,直到所有任务都被遍历。
代码使用了相应的数据结构和算法来实现这一过程,并输出最终排序后的启动任务列表。
时间复杂度:O(N + MlogM),其中N是任务数量,M是依赖关系数量。建图和拓扑排序的过程时间复杂度为O(N + M),排序的时间复杂度为O(MlogM)。 空间复杂度:O(N + M),存储了任务的出度信息和依赖关系。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Map<String, Integer> outdegree = new HashMap<>();
Map<String, List<String>> depend = new HashMap<>();
Scanner scanner = new Scanner(System.in);
String[] relations = scanner.nextLine().split(" ");
// 建立依赖关系,维护出度
for (String relation : relations) {
// a 依赖 b
String[] parts = relation.split("->");
String a = parts[0];
String b = parts[1];
depend.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
outdegree.putIfAbsent(a, 0);
outdegree.putIfAbsent(b, 0);
outdegree.put(a, outdegree.get(a) + 1);
}
// 拓扑排序结果
List<String> rs = new ArrayList<>();
while (true) {
// 找到出度为0的节点,并将其加入结果集中
List<String> temp = new ArrayList<>();
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。