全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：微服务的集成测试
知识点深搜
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
现在有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 进行集成测试
示例1
输入：
3
5 0 0
1 5 0
0 1 5
3
输出：
15
说明：
服务3启动依赖服务2，服务2启动依赖服务1，由于服务1,2,3自身加载需要消耗5s，所以5+5+5=15，需等待15s后可以对服务3进行集成测试
示例2
输入：
3
5 0 0
1 10 1
1 0 11
2
输出：
26
说明：
服务2启动依赖服务1和服务3，服务3启动需要依赖服务1，服务1,2,3自身加载需要消耗5s，10s，11s，所以5+10+11=26s，需等待26s后可以对服务2进行集成测试
示例3
输入：
4
2 0 0 0
0 3 0 0
1 1 4 0
1 1 1 5
4
输出：
12
说明：
服务3启动依赖服务1和服务2，服务4启动需要依赖服务1,2,3，服务1,2,3,4自身加载需要消耗2s，3s，4s，5s,所以3+4+5=12s(因为服务1和服务2可以同时启动)，需等待12s后可以对服务4进行集成测试
示例4
输入：
5
1 0 0 0 0
0 2 0 0 0
1 1 3 0 0
1 1 0 4 0
0 0 1 1 5
5
输出：
11
说明：
服务3启动依赖服务1和服务2，服务4启动需要依赖服务1,2，服务5启动需要依赖服务3,5，服务1,2,3,4,5自身加载需要消耗1s，2s，3s，4s，5s,所以2+4+5=11s(因为服务1和服务2可以同时启动，服务3和服务4可以同时启动)，需等待11s后可以对服务5进行集成测试
解题思路：
通过回溯的方法获取最终启动的服务所依赖的所有服务的启动的时间。
这道题比较难，正确率只有8%。
如示例3：
4
2 0 0 0
0 3 0 0
1 1 4 0
1 1 1 5
4
首先遍历第四行，index=3，times3={}
当i=0时，ints[3][0]==1，依赖服务1，times0={}；
遍历第一行，因为不依赖其他服务，所以最终time0={}，返回0+2;
当i=1时，ints[3][1]==1，依赖服务2，times1={}；
遍历第二行，因为不依赖其他服务，所以最终time1={}，返回0+3;
当i=2时，ints[3][2]==1，依赖服务3，times2={}；
遍历第三行，因为服务1和服务2，所以最终time2={2，3}，取其中最大值3，返回3+4=7;
遍历完成，最终times3={2，3，7}，取其中最大值7，返回7+5=12；
最终结果12。
代码实现：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @title 微服务的集成测试
* @Description 现在有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自身也需要加载），求最少需要等待多少时间。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/14
*/
public class Main {
public static int[][] ints;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ints = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ints[i][j] = sc.nextInt();
}
}
int k = sc.nextInt();
System.out.println(handle(k - 1)); //因为k是行数，在数组中的索引需要-1
}
public static Integer handle(int k) {
List<Integer> times = new ArrayList<>(); //所依赖的服务的启动时间集合
for (int i = 0; i < ints.length; i++) {
if (k != i && ints[k][i] == 1) { //需要剔除服务本身
times.add(handle(i));
}
}
int max = 0; //所依赖的服务的最长启动时间
for (int time : times) {
max = Math.max(max, time);
}
return max + ints[k][k]; //需要加上本身的启动时间
}
}
相关文章
