LeetCode 题解工作台
两天自由外汇交易后的最大货币数
给你一个字符串 initialCurrency ，表示初始货币类型，并且你一开始拥有 1.0 单位的 initialCurrency 。 另给你四个数组，分别表示货币对（字符串）和汇率（实数）： pairs1[i] = [startCurrency i , targetCurrency i ] 表示…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
class Solution: def maxAmount(
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个字符串 initialCurrency，表示初始货币类型，并且你一开始拥有 1.0 单位的 initialCurrency。
另给你四个数组，分别表示货币对（字符串）和汇率（实数）：
pairs1[i] = [startCurrencyi, targetCurrencyi]表示在 第 1 天，可以按照汇率rates1[i]将startCurrencyi转换为targetCurrencyi。pairs2[i] = [startCurrencyi, targetCurrencyi]表示在 第 2 天，可以按照汇率rates2[i]将startCurrencyi转换为targetCurrencyi。- 此外，每种
targetCurrency都可以以汇率1 / rate转换回对应的startCurrency。
你可以在 第 1 天 使用 rates1 进行任意次数的兑换（包括 0 次），然后在 第 2 天 使用 rates2 再进行任意次数的兑换（包括 0 次）。
返回在两天兑换后，最大可能拥有的 initialCurrency 的数量。
注意：汇率是有效的，并且第 1 天和第 2 天的汇率之间相互独立，不会产生矛盾。
示例 1：
输入： initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2.0,3.0], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4.0,5.0,6.0]
输出： 720.00000
解释：
根据题目要求，需要最大化最终的 EUR 数量，从 1.0 EUR 开始：
- 第 1 天：
- 将 EUR 换成 USD，得到 2.0 USD。
- 将 USD 换成 JPY，得到 6.0 JPY。
- 第 2 天：
- 将 JPY 换成 USD，得到 24.0 USD。
- 将 USD 换成 CHF，得到 120.0 CHF。
- 最后将 CHF 换回 EUR，得到 720.0 EUR。
示例 2：
输入： initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]
输出： 1.50000
解释：
在第 1 天将 NGN 换成 EUR，并在第 2 天用反向汇率将 EUR 换回 NGN，可以最大化最终的 NGN 数量。
示例 3：
输入： initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]
输出： 1.00000
解释：
在这个例子中，不需要在任何一天进行任何兑换。
提示：
1 <= initialCurrency.length <= 3initialCurrency仅由大写英文字母组成。1 <= n == pairs1.length <= 101 <= m == pairs2.length <= 10pairs1[i] == [startCurrencyi, targetCurrencyi]pairs2[i] == [startCurrencyi, targetCurrencyi]1 <= startCurrencyi.length, targetCurrencyi.length <= 3startCurrencyi和targetCurrencyi仅由大写英文字母组成。rates1.length == nrates2.length == m1.0 <= rates1[i], rates2[i] <= 10.0- 输入保证两个转换图在各自的天数中没有矛盾或循环。
- 输入保证输出 最大 为
5 * 1010。
解题思路
方法一
class Solution:
def maxAmount(
self,
initialCurrency: str,
pairs1: List[List[str]],
rates1: List[float],
pairs2: List[List[str]],
rates2: List[float],
) -> float:
d1 = self.build(pairs1, rates1, initialCurrency)
d2 = self.build(pairs2, rates2, initialCurrency)
return max(d1.get(a, 0) / r2 for a, r2 in d2.items())
def build(
self, pairs: List[List[str]], rates: List[float], init: str
) -> Dict[str, float]:
def dfs(a: str, v: float):
d[a] = v
for b, r in g[a]:
if b not in d:
dfs(b, v * r)
g = defaultdict(list)
for (a, b), r in zip(pairs, rates):
g[a].append((b, r))
g[b].append((a, 1 / r))
d = {}
dfs(init, 1)
return d
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of currencies and conversion pairs for both days, roughly O(n*m) in the worst case due to DFS traversals. Space complexity is proportional to graph size and recursive call stack, O(n+m). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the problem requires exploring all possible intermediate currencies for two-step conversions.
- question_mark
Recognize that cycles are absent, but handling multiple paths is crucial to avoid underestimating the maximum.
- question_mark
Focus on depth-first search traversal as the core pattern to find maximal cumulative rates.
常见陷阱
外企场景- error
Failing to consider all intermediate currencies can lead to suboptimal results.
- error
Multiplying rates incorrectly across day 1 and day 2 conversions reduces the final amount.
- error
Ignoring disconnected currencies or paths that return to initialCurrency may miss the maximum achievable value.
进阶变体
外企场景- arrow_right_alt
Extend to three or more days of conversions with additional graphs and sequential DFS traversals.
- arrow_right_alt
Optimize using memoization to store maximum amounts for intermediate currencies to avoid repeated DFS computations.
- arrow_right_alt
Allow bidirectional conversion rates explicitly to increase reachable paths and maximize returns.