How do I approach the 'Unit Conversion I' problem?

Focus on representing the units and conversions as a graph. Use DFS to traverse the graph and compute the conversion factor for each unit with respect to the base unit.

What pattern is most useful for solving the 'Unit Conversion I' problem?

Graph traversal using Depth-First Search (DFS) is the key pattern to solve this problem. The problem is essentially about finding paths in a weighted directed tree.

Why do we need to use modulo in 'Unit Conversion I'?

Modulo 10^9 + 7 is used to prevent overflow since the conversion factors can become very large. It ensures that the output fits within the constraints.

What is the best way to represent the conversions in 'Unit Conversion I'?

Use an adjacency list to represent the graph, where each node corresponds to a unit, and the edges store the conversion factors between units.

How does DFS help in solving 'Unit Conversion I'?

DFS allows you to traverse the graph starting from unit 0 and calculate the conversion factor for each unit by multiplying the conversion factors along the path.

#3528

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

单位转换 I

有 n 种单位，编号从 0 到 n - 1 。给你一个二维整数数组 conversions ，长度为 n - 1 ，其中 conversions[i] = [sourceUnit i , targetUnit i , conversionFactor i ] ，表示一个 sourceUnit i 类…

深度优先搜索广度优先搜索图

题目描述

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

请你返回一个长度为 n 的数组 baseUnitConversion，其中 baseUnitConversion[i] 表示一个 0 类型单位等于多少个 i 类型单位。由于结果可能很大，请返回每个 baseUnitConversion[i] 对 10⁹ + 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]

解释：

使用 conversions[0] 将一个 0 类型单位转换为 2 个 1 类型单位。
使用 conversions[1] 将一个 0 类型单位转换为 3 个 2 类型单位。
使用 conversions[0] 和 conversions[2] 将一个 0 类型单位转换为 8 个 3 类型单位。
使用 conversions[0] 和 conversions[3] 将一个 0 类型单位转换为 10 个 4 类型单位。
使用 conversions[1] 和 conversions[4] 将一个 0 类型单位转换为 6 个 5 类型单位。
使用 conversions[0]、conversions[3] 和 conversions[5] 将一个 0 类型单位转换为 30 个 6 类型单位。
使用 conversions[1]、conversions[4] 和 conversions[6] 将一个 0 类型单位转换为 24 个 7 类型单位。

提示：

2 <= n <= 10⁵
conversions.length == n - 1
0 <= sourceUnit_i, targetUnit_i < n
1 <= conversionFactor_i <= 10⁹
保证单位 0 可以通过唯一的转换路径（不需要反向转换）转换为任何其他单位。

lightbulb

解题思路

方法一：DFS

由于题目保证了单位 0 可以通过唯一的转换路径转换为其他单位，因此我们可以使用深度优先搜索（DFS）来遍历所有单位的转换关系。另外，由于 $\textit{conversions}$ 数组的长度为 $n - 1$ ，表示有 $n - 1$ 条转换关系，因此我们可以将单位转换关系看作一棵树，根节点为单位 0，其他节点为其他单位。

我们可以用一个邻接表 $g$ 来表示单位转换关系，其中 $g[i]$ 表示单位 $i$ 可以转换到的单位和对应的转换因子。

然后，我们从根节点 $0$ 开始进行深度优先搜索，即调函数 $\textit{dfs}(s, \textit{mul})$ ，其中 $s$ 表示当前单位， $\textit{mul}$ 表示从单位 $0$ 转换到单位 $s$ 的转换因子。初始时 $s = 0$ , $\textit{mul} = 1$ 。在每次递归中，我们将当前单位 $s$ 的转换因子 $\textit{mul}$ 存储到答案数组中，然后遍历当前单位 $s$ 的所有邻接单位 $t$ ，递归调用 $\textit{dfs}(t, \textit{mul} \times w \mod (10^9 + 7))$ ，其中 $w$ 为单位 $s$ 转换到单位 $t$ 的转换因子。

最后，我们返回答案数组即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为单位的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        def dfs(s: int, mul: int) -> None:
            ans[s] = mul
            for t, w in g[s]:
                dfs(t, mul * w % mod)

        mod = 10**9 + 7
        n = len(conversions) + 1
        g = [[] for _ in range(n)]
        for s, t, w in conversions:
            g[s].append((t, w))
        ans = [0] * n
        dfs(0, 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate's ability to identify graph traversal as the solution approach will be key.
question_mark
Look for their understanding of Depth-First Search as it applies to this problem's structure.
question_mark
Candidates should demonstrate an understanding of modular arithmetic when handling large numbers in the output.

warning

常见陷阱

外企场景

error
Not correctly using modulo 10^9 + 7, leading to overflow.
error
Misunderstanding the conversion relationships between units and failing to propagate conversion factors through the graph.
error
Not handling recursion depth properly in DFS or running into stack overflow for large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjusting the problem to handle bidirectional conversions between units.
arrow_right_alt
Expanding the problem to handle more complex graph structures with cycles.
arrow_right_alt
Optimizing for space and time complexity when the number of units is very large.

help

常见问题

外企场景

继续练习

#3493 属性图 #3607 电网维护 #3419 图的最大边权的最小值