Medium

题目描述

有 n 种单位，编号从 0 到 n - 1。给你一个长度为 n - 1 的二维整数数组 conversions，其中 conversions[i] = [sourceUniti, targetUniti, conversionFactori]。这表示一个 sourceUniti 类型的单位等价于 conversionFactori 个 targetUniti 类型的单位。

返回一个长度为 n 的数组 baseUnitConversion，其中 baseUnitConversion[i] 是与一个类型 0 的单位等价的类型 i 的单位数量。由于答案可能很大，返回每个 baseUnitConversion[i] 模 10^9 + 7 的结果。

示例 1：

输入：conversions = [[0,1,2],[1,2,3]]
输出：[1,2,6]
解释：
- 使用 conversions[0] 将一个类型 0 的单位转换为 2 个类型 1 的单位。
- 使用 conversions[0] 然后 conversions[1] 将一个类型 0 的单位转换为 6 个类型 2 的单位。

示例 2：

输入：conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
输出：[1,2,3,8,10,6,30,24]

约束条件：

  • 2 <= n <= 10^5
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 10^9
  • 保证单位 0 可以通过唯一的转换组合转换为任何其他单位，而不使用反向转换。

解题思路

根据题目描述，这是一个图论问题，可以将单位转换关系建模为一棵有根树，其中根节点是单位 0。

思路分析：

  1. 建图阶段：根据 conversions 数组构建邻接表，每条边代表一个转换关系，权重为转换因子。

  2. 遍历求解：从根节点 0 开始进行 BFS 或 DFS 遍历，计算从根节点到每个节点的路径权重乘积，这个乘积就是该节点对应单位与单位 0 的转换比例。

  3. 处理大数：由于转换因子可能很大，需要在计算过程中取模防止溢出。

具体步骤：

  • 构建邻接表存储图的边和权重
  • 使用 BFS 从节点 0 开始遍历，初始化结果数组，节点 0 对应值为 1
  • 对于每个相邻节点，新的转换值 = 当前节点转换值 × 边的权重
  • 所有计算结果都要对 10^9 + 7 取模

推荐使用 BFS 解法，代码简洁且易于理解。

代码实现

class Solution {
public:
    vector<int> baseUnitConversions(vector<vector<int>>& conversions) {
        int n = conversions.size() + 1;
        const int MOD = 1e9 + 7;
        
        vector<vector<pair<int, long long>>> graph(n);
        for (auto& conv : conversions) {
            graph[conv[0]].push_back({conv[1], conv[2]});
        }
        
        vector<long long> result(n, 0);
        result[0] = 1;
        
        queue<int> q;
        q.push(0);
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            for (auto& [next, factor] : graph[curr]) {
                result[next] = (result[curr] * factor) % MOD;
                q.push(next);
            }
        }
        
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = result[i];
        }
        return ans;
    }
};

class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        n = len(conversions) + 1
        MOD = 10**9 + 7
        
        graph = [[] for _ in range(n)]
        for source, target, factor in conversions:
            graph[source].append((target, factor))
        
        result = [0] * n
        result[0] = 1
        
        queue = [0]
        
        while queue:
            curr = queue.pop(0)
            
            for next_unit, factor in graph[curr]:
                result[next_unit] = (result[curr] * factor) % MOD
                queue.append(next_unit)
        
        return result

public class Solution {
    public int[] BaseUnitConversions(int[][] conversions) {
        int n = conversions.Length + 1;
        const int MOD = 1000000007;
        
        List<(int, long)>[] graph = new List<(int, long)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, long)>();
        }
        
        foreach (var conv in conversions) {
            graph[conv[0]].Add((conv[1], conv[2]));
        }
        
        long[] result = new long[n];
        result[0] = 1;
        
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        
        while (queue.Count > 0) {
            int curr = queue.Dequeue();
            
            foreach (var (next, factor) in graph[curr]) {
                result[next] = (result[curr] * factor) % MOD;
                queue.Enqueue(next);
            }
        }
        
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = (int)result[i];
        }
        return ans;
    }
}

var baseUnitConversions = function(conversions) {
    const n = conversions.length + 1;
    const MOD = 1e9 + 7;
    
    const graph = Array(n).fill(null).map(() => []);
    for (const [source, target, factor] of conversions) {
        graph[source].push([target, factor]);
    }
    
    const result = new Array(n).fill(0);
    result[0] = 1;
    
    const queue = [0];
    
    while (queue.length > 0) {
        const curr = queue.shift();
        
        for (const [next, factor] of graph[curr]) {
            result[next] = (result[curr] * factor) % MOD;
            queue.push(next);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是单位数量。每个节点和边都只访问一次
空间复杂度O(n)，用于存储图的邻接表、结果数组和队列