【华为OD】微服务的集成测试

发布于：2025-09-10 ⋅ 阅读:(14) ⋅ 点赞:(0)

【华为OD】微服务的集成测试

题目描述

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

给你一个 n×n 的二维矩阵 useTime，其中 useTime[i][i] = 10 表示服务 i 自身启动加载需要消耗 10 s，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 进行集成测试

示例

示例一

输入：

3
5 0 0
1 5 0
0 1 5
3

输出：

15

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

示例二

输入：

3
5 0 0
1 10 1
1 0 11
2

输出：

26

说明：
服务 2 启动依赖服务 1 和服务 3，服务 3 启动需要依赖服务 1，服务 1,2,3 自身加载需要消耗 5 s，10 s，11 s，所以 5+10+11=26，需等待 26 s 后可以对服务 2 进行集成测试

示例三

输入：

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

解题思路

这是一个典型的有向无环图（DAG）的关键路径问题。我们需要找到从所有依赖服务到目标服务的最长路径，因为所有依赖服务都必须完成后，目标服务才能启动。

核心思想：

  1. 将服务依赖关系建模为有向图
  2. 使用拓扑排序或DFS计算每个服务的最早完成时间
  3. 目标服务的最早完成时间就是答案

我将提供两种解法：拓扑排序法（BFS）和深度优先搜索法（DFS）。

解法一：拓扑排序法（BFS）

使用拓扑排序的思想，从入度为0的节点开始，逐层计算每个服务的最早完成时间。

Java实现

import java.util.*;

public class Solution1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] useTime = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                useTime[i][j] = sc.nextInt();
            }
        }
        
        int k = sc.nextInt() - 1; // 转换为0基索引
        
        int result = calculateMinTime(useTime, k, n);
        System.out.println(result);
        
        sc.close();
    }
    
    private static int calculateMinTime(int[][] useTime, int target, int n) {
        // 构建依赖图和入度数组
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 构建图：如果服务i依赖服务j，则j->i有边
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && useTime[i][j] > 0) {
                    graph.get(j).add(i);
                    inDegree[i]++;
                }
            }
        }
        
        // 拓扑排序计算最早完成时间
        int[] finishTime = new int[n];
        Queue<Integer> queue = new LinkedList<>();
        
        // 将入度为0的节点加入队列
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                finishTime[i] = useTime[i][i]; // 自身启动时间
            }
        }
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int next : graph.get(current)) {
                // 更新依赖服务的最早完成时间
                finishTime[next] = Math.max(finishTime[next], 
                    finishTime[current] + useTime[next][next]);
                
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return finishTime[target];
    }
}

Python实现

from collections import deque

def calculate_min_time(use_time, target, n):
    # 构建依赖图和入度数组
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    
    # 构建图：如果服务i依赖服务j，则j->i有边
    for i in range(n):
        for j in range(n):
            if i != j and use_time[i][j] > 0:
                graph[j].append(i)
                in_degree[i] += 1
    
    # 拓扑排序计算最早完成时间
    finish_time = [0] * n
    queue = deque()
    
    # 将入度为0的节点加入队列
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
            finish_time[i] = use_time[i][i]  # 自身启动时间
    
    while queue:
        current = queue.popleft()
        
        for next_service in graph[current]:
            # 更新依赖服务的最早完成时间
            finish_time[next_service] = max(finish_time[next_service],
                                          finish_time[current] + use_time[next_service][next_service])
            
            in_degree[next_service] -= 1
            if in_degree[next_service] == 0:
                queue.append(next_service)
    
    return finish_time[target]

def solve_topological():
    n = int(input())
    use_time = []
    
    for _ in range(n):
        row = list(map(int, input().split()))
        use_time.append(row)
    
    k = int(input()) - 1  # 转换为0基索引
    
    result = calculate_min_time(use_time, k, n)
    print(result)

solve_topological()

C++实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int calculateMinTime(vector<vector<int>>& useTime, int target, int n) {
    // 构建依赖图和入度数组
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);
    
    // 构建图：如果服务i依赖服务j，则j->i有边
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && useTime[i][j] > 0) {
                graph[j].push_back(i);
                inDegree[i]++;
            }
        }
    }
    
    // 拓扑排序计算最早完成时间
    vector<int> finishTime(n, 0);
    queue<int> q;
    
    // 将入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            finishTime[i] = useTime[i][i]; // 自身启动时间
        }
    }
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int next : graph[current]) {
            // 更新依赖服务的最早完成时间
            finishTime[next] = max(finishTime[next],
                finishTime[current] + useTime[next][next]);
            
            inDegree[next]--;
            if (inDegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    return finishTime[target];
}

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> useTime(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> useTime[i][j];
        }
    }
    
    int k;
    cin >> k;
    k--; // 转换为0基索引
    
    int result = calculateMinTime(useTime, k, n);
    cout << result << endl;
    
    return 0;
}

解法二：深度优先搜索法（DFS）

使用DFS递归计算每个服务的最早完成时间，通过记忆化搜索避免重复计算。

Java实现

import java.util.*;

public class Solution2 {
    private static int[][] useTime;
    private static int[] memo;
    private static int n;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        useTime = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                useTime[i][j] = sc.nextInt();
            }
        }
        
        int k = sc.nextInt() - 1; // 转换为0基索引
        
        memo = new int[n];
        Arrays.fill(memo, -1);
        
        int result = dfs(k);
        System.out.println(result);
        
        sc.close();
    }
    
    private static int dfs(int service) {
        if (memo[service] != -1) {
            return memo[service];
        }
        
        int maxDependencyTime = 0;
        
        // 查找所有依赖服务
        for (int j = 0; j < n; j++) {
            if (j != service && useTime[service][j] > 0) {
                maxDependencyTime = Math.max(maxDependencyTime, dfs(j));
            }
        }
        
        // 当前服务的最早完成时间 = 最大依赖完成时间 + 自身启动时间
        memo[service] = maxDependencyTime + useTime[service][service];
        return memo[service];
    }
}

Python实现

def dfs(service, use_time, memo, n):
    if memo[service] != -1:
        return memo[service]
    
    max_dependency_time = 0
    
    # 查找所有依赖服务
    for j in range(n):
        if j != service and use_time[service][j] > 0:
            max_dependency_time = max(max_dependency_time, dfs(j, use_time, memo, n))
    
    # 当前服务的最早完成时间 = 最大依赖完成时间 + 自身启动时间
    memo[service] = max_dependency_time + use_time[service][service]
    return memo[service]

def solve_dfs():
    n = int(input())
    use_time = []
    
    for _ in range(n):
        row = list(map(int, input().split()))
        use_time.append(row)
    
    k = int(input()) - 1  # 转换为0基索引
    
    memo = [-1] * n
    result = dfs(k, use_time, memo, n)
    print(result)

solve_dfs()

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> useTime;
vector<int> memo;
int n;

int dfs(int service) {
    if (memo[service] != -1) {
        return memo[service];
    }
    
    int maxDependencyTime = 0;
    
    // 查找所有依赖服务
    for (int j = 0; j < n; j++) {
        if (j != service && useTime[service][j] > 0) {
            maxDependencyTime = max(maxDependencyTime, dfs(j));
        }
    }
    
    // 当前服务的最早完成时间 = 最大依赖完成时间 + 自身启动时间
    memo[service] = maxDependencyTime + useTime[service][service];
    return memo[service];
}

int main() {
    cin >> n;
    
    useTime.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> useTime[i][j];
        }
    }
    
    int k;
    cin >> k;
    k--; // 转换为0基索引
    
    memo.resize(n, -1);
    int result = dfs(k);
    cout << result << endl;
    
    return 0;
}

解法三：优化的拓扑排序法

对拓扑排序进行优化，使代码更加简洁高效。

Java实现

import java.util.*;

public class Solution3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        
        int target = sc.nextInt() - 1;
        
        System.out.println(solve(matrix, target, n));
        sc.close();
    }
    
    private static int solve(int[][] matrix, int target, int n) {
        // 构建邻接表和入度
        List<Integer>[] graph = new List[n];
        int[] inDegree = new int[n];
        int[] finishTime = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && matrix[i][j] > 0) {
                    graph[j].add(i);
                    inDegree[i]++;
                }
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                finishTime[i] = matrix[i][i];
            }
        }
        
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int next : graph[curr]) {
                finishTime[next] = Math.max(finishTime[next], 
                    finishTime[curr] + matrix[next][next]);
                if (--inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        return finishTime[target];
    }
}

Python实现

from collections import deque

def solve(matrix, target, n):
    # 构建邻接表和入度
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    finish_time = [0] * n
    
    for i in range(n):
        for j in range(n):
            if i != j and matrix[i][j] > 0:
                graph[j].append(i)
                in_degree[i] += 1
    
    queue = deque()
    for i in range(n):
        if in_degree[i] == 0:
            queue.append(i)
            finish_time[i] = matrix[i][i]
    
    while queue:
        curr = queue.popleft()
        for next_node in graph[curr]:
            finish_time[next_node] = max(finish_time[next_node],
                                       finish_time[curr] + matrix[next_node][next_node])
            in_degree[next_node] -= 1
            if in_degree[next_node] == 0:
                queue.append(next_node)
    
    return finish_time[target]

def main():
    n = int(input())
    matrix = []
    for _ in range(n):
        row = list(map(int, input().split()))
        matrix.append(row)
    
    target = int(input()) - 1
    print(solve(matrix, target, n))

main()

C++实现

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solve(vector<vector<int>>& matrix, int target, int n) {
    // 构建邻接表和入度
    vector<vector<int>> graph(n);
    vector<int> inDegree(n, 0);
    vector<int> finishTime(n, 0);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && matrix[i][j] > 0) {
                graph[j].push_back(i);
                inDegree[i]++;
            }
        }
    }
    
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
            finishTime[i] = matrix[i][i];
        }
    }
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        for (int next : graph[curr]) {
            finishTime[next] = max(finishTime[next],
                finishTime[curr] + matrix[next][next]);
            if (--inDegree[next] == 0) {
                q.push(next);
            }
        }
    }
    
    return finishTime[target];
}

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }
    
    int target;
    cin >> target;
    target--; // 转换为0基索引
    
    cout << solve(matrix, target, n) << endl;
    return 0;
}

算法复杂度分析

解法一：拓扑排序法（BFS）

  • 时间复杂度：O(N²)，需要构建图和进行拓扑排序
  • 空间复杂度：O(N²)，存储邻接表和辅助数组

解法二：深度优先搜索法（DFS）

  • 时间复杂度：O(N²)，每个节点最多访问一次，每次访问需要检查所有依赖
  • 空间复杂度：O(N)，递归栈深度和记忆化数组

解法三：优化的拓扑排序法

  • 时间复杂度：O(N²)，与标准拓扑排序相同
  • 空间复杂度：O(N²)，但代码更简洁

算法原理详解

核心思想

这个问题本质上是求有向无环图中的关键路径长度。每个服务可以看作图中的一个节点，依赖关系构成有向边，服务的启动时间是节点的权重。

关键概念

  1. 依赖关系建模：如果服务A依赖服务B，则从B到A有一条有向边
  2. 最早完成时间：服务的最早完成时间 = max(所有依赖服务的完成时间) + 自身启动时间
  3. 并行启动：没有依赖关系的服务可以并行启动

两种解法的区别

  1. 拓扑排序法：

    • 从入度为0的节点开始，逐层计算
    • 适合理解服务启动的时间顺序
    • 代码结构清晰，易于调试

  2. DFS法：

    • 从目标节点开始，递归计算依赖
    • 使用记忆化避免重复计算
    • 代码更简洁，但递归深度可能较大

示例分析

示例三详细分析

服务依赖关系：

服务1: 启动时间2s，无依赖
服务2: 启动时间3s，无依赖  
服务3: 启动时间4s，依赖服务1和服务2
服务4: 启动时间5s，依赖服务1、服务2和服务3

启动时序：

  1. t=0: 服务1和服务2并行启动
  2. t=2: 服务1完成启动
  3. t=3: 服务2完成启动，服务3开始启动
  4. t=7: 服务3完成启动（3+4=7），服务4开始启动
  5. t=12: 服务4完成启动（7+5=12）

所以答案是12秒。

示例四详细分析

服务依赖关系：

服务1: 启动时间1s，无依赖
服务2: 启动时间2s，无依赖
服务3: 启动时间3s，依赖服务1和服务2
服务4: 启动时间4s，依赖服务1和服务2
服务5: 启动时间5s，依赖服务3和服务4

启动时序：

  1. t=0: 服务1和服务2并行启动
  2. t=1: 服务1完成启动
  3. t=2: 服务2完成启动，服务3和服务4并行启动
  4. t=5: 服务3完成启动（2+3=5）
  5. t=6: 服务4完成启动（2+4=6），服务5开始启动
  6. t=11: 服务5完成启动（6+5=11）

所以答案是11秒。

优化技巧

1. 输入处理优化

// 可以在读入时直接构建图，避免二次遍历
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int val = sc.nextInt();
        if (i == j) {
            selfTime[i] = val;
        } else if (val > 0) {
            graph[j].add(i);
            inDegree[i]++;
        }
    }
}

2. 边界条件处理

// 处理目标服务无依赖的情况
if (inDegree[target] == 0) {
    return matrix[target][target];
}

3. 内存优化

对于大规模数据，可以使用邻接表代替邻接矩阵存储图结构，节省空间。

总结

两种解法都能正确解决问题，选择建议：

  1. 拓扑排序法：

    • 逻辑清晰，易于理解和调试
    • 适合对算法过程有清晰认知的场景
    • 推荐用于面试和学习

  2. DFS法：

    • 代码简洁，实现快速
    • 适合竞赛等对编码速度要求高的场景
    • 需要注意递归深度限制

核心要点：

  • 正确理解依赖关系的建模方式
  • 掌握拓扑排序和DFS两种图算法
  • 注意并行启动的处理逻辑
  • 仔细处理输入格式和索引转换

对于华为OD机试，建议掌握拓扑排序法，因为它更容易验证正确性，且在面试中能更好地展示算法思维。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布