【华为OD机考】华为OD笔试真题解析(16)--微服务的集成测试

题目描述

现在有n个容器服务，服务的启动可能有一定的依赖性（有些服务启动没有依赖），其次，服务自身启动加载会消耗一些时间。

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

输入描述

第一行输入服务总量n，之后的n行表示服务启动的依赖关系以及自身启动加载耗时，最后输入k表示计算需要等待多少时间后，可以对服务k进行集成测试，其中1 <= k <= n, 1 <= n <= 100。

输出描述

最少需要等待多少时间（单位：秒）后，可以对服务k进行集成测试。

示例描述 示例一

输入：

3 5 0 0 1 5 0 0 1 5 3

输出：

15

说明： 服务3启动依赖服务2，服务2启动依赖服务1，由于服务1、2、3自身加载都需要消耗5s，所以5+5+5=15s，需要等待15s后可以对服务3进行集成测试。

示例二

输入：

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进行集成测试。

示例三

输入：

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进行集成测试。

示例四

输入：

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和服务4，服务1、2、3、4、5自身加载需要消耗1s、2s、3s、4s、5s，所以2+4+5=11s（因为服务1和服务2可以同时启动，服务3和服务4可以同时启动），需要等待11s后可以对服务5进行集成测试。

解题思路 本题使用深度优先遍历DFS进行解题；调用深度优先遍历，返回总耗时深度优先遍历： 确认递归函数的参数：参数包括服务k、服务耗时矩阵arr。终止条件：当查找不到启动依赖服务终止，返回耗时，并加上服务自身耗时。处理：遍历服务，得到服务k启动依赖的服务。递归遍历，计算下一层依赖服务的耗时，得到总最大服务耗时时间。 返回服务总耗时时间。 解题代码 def dfs(arr, k): max_time = 0 # 遍历服务 for i in range(len(arr)): # 得到服务k启动依赖的服务 if arr[k][i] != 0 and i != k: # 计算启动依赖服务的最大耗时，并记录到总耗时中 max_time = max(max_time, dfs(arr, i)) return max_time + arr[k][k] def solve_method(arr, k): total_time = dfs(arr, k - 1) return total_time if __name__ == '__main__': k = 3 useTime = [ [5, 0, 0], [1, 5, 0], [0, 1, 5] ] assert solve_method(useTime, k) == 15 k = 2 useTime = [ [5, 0, 0], [1, 10, 1], [1, 0, 11] ] assert solve_method(useTime, k) == 26 k = 4 useTime = [ [2, 0, 0, 0], [0, 3, 0, 0], [1, 1, 4, 0], [1, 1, 1, 5], ] assert solve_method(useTime, k) == 12 k = 5 useTime = [ [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] ] assert solve_method(useTime, k) == 11