华为OD机试真题 Java 实现【微服务的集成测试】【2023Q1 100分】

在这里插入图片描述

一、题目描述

现在有n个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次服务自身启动加载会消耗一些时间。
给你一个 nxn 的二维矩阵 useTime，其中 useTime[i][i]=10 表示服务 i 自身启动加载需要消耗10s，useTime[i][j]=1 表示服务 i 启动依赖 j 启动完成，useTime[i][k]=0，表示服务 i 启动不依赖服务 k，其实0 <= i,j,k <n。服务之间启动没有循环依赖，若想对任意一个服务 i 进行集成测试（服务 i 自身也需要加载），求最少需要等待多长时间。

二、输入描述

第一行输入服务总量n，之后的 n 行表示服务启动的依赖关系以及自身启动加载耗时。

最后一行输入 k 表示计算需要等待多长时间后可以对服务 k 进行集成测试。

其中 1 <= k <= n，1 <= n <= 100。

三、输出描述

最少需要等待多长时间(s)后可以对服务 k 进行集成测试。

四、Java算法源码

java">public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] nums = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            nums[i][j] = sc.nextInt();
        }
    }
    int k = sc.nextInt();
    //从第K个服务，对应到数组行数就是k-1
    int time = needTime(nums, k - 1);
    System.out.println(time);

}

//获取当前服务的需要等待的最少时间
public static int needTime(int[][] nums, int k) {
    int n = nums[0].length;

    int selfTime = nums[k][k];
    int dependMaxTime = 0;
    for (int i = 0; i < n; i++) {
        if (nums[k][i] == 1 && i != k) {
            int time = needTime(nums, i);
            dependMaxTime = Math.max(dependMaxTime, time);
        }
    }
    return selfTime + dependMaxTime;
}