【华为OD题库-099】服务启动-java

题目

有若干个连续编号的服务（编号从O开始)，服务间有依赖关系，启动一个指定服务，请判断该服务是否可以成功启动，并输出以来的前置服务编号（依赖关系是可以传递的，比如服务2依赖服务1，服务1依赖于服务0，那么服务2依赖于服务1和服务0)。
输入描述
第一行输入为N，N为服务的总个数（1<=N<= 5000)
第二行输入为M，M为指定启动服务的编号(0<=M<5000)
接下来的N行，是从编号0服务~编号N-1服务的服务依赖表，每一行第一个数字是该服务依赖的服务个数T(0 <=T<5000)后面T个数字分别是对应的依赖服务编号
输出描述
为了避免不同算法的服务加载顺序不同，请从服务编号从小到大以此输出所有前置服务的编号，不包括指定启动的服务编号自身。
如果没有依赖的前置服务则输出null。
如果服务无法启动（出现循环依赖，则服务无法启动，样例2为最简单的循环依赖）或其它异常，输出-1.
样例1
输入
4
2
0
1,0
1,1
2,0,1
输出
0,1
解释:
第一行，4，一共四个服务，编号0~3
第二行，2，指定启动编号为2的服务
第三行开始为服务依赖关系表
第三行，0，表示服务0，没有依赖的前置任务，依赖个数为0
第四行，1,0，表示服务1，依赖1个前置任务，编号为0
第三行，1,1，表示服务2，依赖1个前置任务，编号为1
第三行，2,1,0表示服务3，依赖2个前置任务，编号为0和1
分析，服务启动顺序为0，1，2，可成功启动服务2，输出0，1
样例2
输入
2
1
1,1
1,0
输出
-1

思路

题目要求输出的服务不重复且有序，可以考虑使用TreeSet存储
先将输入直接存入int[][] services数组，services[m]代表第m个服务的依赖关系，其中services[m][0]代表m依赖的服务关系数量，后续代表具体依赖的服务编号
通读题目可发现是典型的dfs问题，比如1依赖2,2依赖3，3无依赖，启动1需要启动哪些服务？先找到2，再根据2找3，找到3时无依赖，最后输出2,3。
同时需要注意在找某条路径时，是否存在重复数字，比如找出来的是1,2,3,2，那么存在循环依赖，直接返回-1
再处理无依赖的情况，输出null

题解

package hwod;

import java.util.*;


public class ServiceStart {
    //treeSet有序且不重复
    private static Set<Integer> ans = new TreeSet<>();
    private static int target;
    private static boolean isLoopDep = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        target = sc.nextInt();
        sc.nextLine();
        int[][] services = new int[n][];
        for (int i = 0; i < n; i++) {
            services[i] = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        }
        serviceStart(services);
        if (ans.size() == 0) {
            System.out.println("null");
            return;
        }
        if (isLoopDep) {
            System.out.println("-1");
            return;
        }

        //treeset不能通过索引遍历，为了便于控制输出格式，转化为数组
        Integer[] nums = ans.toArray(new Integer[0]);
        for (int i = 0; i < nums.length; i++) {
            if (i != 0) System.out.print(",");
            System.out.print(nums[i]);
        }


    }


    private static void serviceStart(int[][] services) {
        int[] path = new int[services.length];//判断某个路径上是否有重复依赖
        dfs(services, target, path);
    }

    private static void dfs(int[][] services, int m, int path[]) {

        if (path[m] == 1) {
            //说明存在循环依赖
            isLoopDep = true;
            return;
        }
        if (m != target) ans.add(m);
        for (int i = 0; i < services[m][0]; i++) {
            if (isLoopDep) break;
            path[m] = 1;
            dfs(services, services[m][i + 1], path);
            path[m] = 0;
        }
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。