2025-07-01：两天自由外汇交易后的最大货币数。用go语言，你有一个字符串 initialCurrency，表示你最开始拥有的货币种类，且初始数量是 1.0 单位。

另外，有两个交易日的货币兑换信息：

第一天的兑换对 pairs1，数组中每个元素是一个 [startCurrency, targetCurrency]，表示当天你可以用汇率 rates1[i] 将 startCurrency 换成 targetCurrency。

第二天的兑换对 pairs2，其中的 [startCurrency, targetCurrency] 与对应汇率 rates2[i] 同理。

每种货币对的兑换是双向的，也就是说不仅可以按 rate 从 startCurrency 换到 targetCurrency，也可以用汇率 1 / rate 反向兑换。

在第 1 天，你可以进行任意次数（包括 0 次）的兑换，利用 pairs1 和 rates1。然后在第 2 天，再利用 pairs2 和 rates2 同样进行任意次数的兑换。

你的任务是计算，经过这两天的兑换后，能够获得的最多的最初货币（initialCurrency）的数量。
汇率有效且两天的汇率不会互相矛盾。

1 <= initialCurrency.length <= 3。

initialCurrency 仅由大写英文字母组成。

1 <= n == pairs1.length <= 10。

1 <= m == pairs2.length <= 10。

pairs1[i] == [startCurrencyi, targetCurrencyi]。

pairs2[i] == [startCurrencyi, targetCurrencyi]。

1 <= startCurrencyi.length, targetCurrencyi.length <= 3。

startCurrencyi 和 targetCurrencyi 仅由大写英文字母组成。

rates1.length == n。

rates2.length == m。

1.0 <= rates1[i], rates2[i] <= 10.0。

输入保证两个转换图在各自的天数中没有矛盾或循环。

输入保证输出 最大 为 5 * 10000000000。

输入： 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。

题目来自力扣3387。

解决思路

为了最大化最终的 initialCurrency 数量，我们需要：

1. 第一天：找到从 initialCurrency 到所有其他货币的最佳兑换路径，即计算从 initialCurrency 出发到所有其他货币的兑换率。
2. 第二天：找到从所有其他货币回到 initialCurrency 的最佳兑换路径，即计算从所有其他货币出发到 initialCurrency 的兑换率。
3. 组合两天：对于每一种货币，计算第一天从 initialCurrency 兑换到该货币的数量，然后第二天从该货币兑换回 initialCurrency 的数量，取最大值。

详细步骤

第一步：构建第一天的兑换图并计算兑换率

1. 构建图：

   • 将 pairs1 和 rates1 转换为图结构。对于每一对 [startCurrency, targetCurrency] 和对应的 rate：
     • 添加从 startCurrency 到 targetCurrency 的边，权重为 rate。
     • 添加从 targetCurrency 到 startCurrency 的边，权重为 1 / rate。
   • 例如：
     • ["EUR", "USD"] 和 rate = 2.0：
       • EUR -> USD：2.0
       • USD -> EUR：1 / 2.0 = 0.5
     • ["USD", "JPY"] 和 rate = 3.0：
       • USD -> JPY：3.0
       • JPY -> USD：1 / 3.0 ≈ 0.333

2. 计算兑换率：

   • 从 initialCurrency（“EUR”）出发，使用深度优先搜索（DFS）或广度优先搜索（BFS）计算到所有其他货币的兑换率。
   • 初始化 amount 字典：{"EUR": 1.0}。
   • 从 “EUR” 开始 DFS：
     • “EUR” 可以兑换 “USD”：amount["USD"] = amount["EUR"] * 2.0 = 2.0。
     • 从 “USD” 可以兑换 “JPY”：amount["JPY"] = amount["USD"] * 3.0 = 6.0。
   • 最终 amount：
     • {"EUR": 1.0, "USD": 2.0, "JPY": 6.0}。

第二步：构建第二天的兑换图并计算兑换率

1. 构建图：

   • 将 pairs2 和 rates2 转换为图结构。对于每一对 [startCurrency, targetCurrency] 和对应的 rate：
     • 添加从 startCurrency 到 targetCurrency 的边，权重为 rate。
     • 添加从 targetCurrency 到 startCurrency 的边，权重为 1 / rate。
   • 例如：
     • ["JPY", "USD"] 和 rate = 4.0：
       • JPY -> USD：4.0
       • USD -> JPY：1 / 4.0 = 0.25
     • ["USD", "CHF"] 和 rate = 5.0：
       • USD -> CHF：5.0
       • CHF -> USD：1 / 5.0 = 0.2
     • ["CHF", "EUR"] 和 rate = 6.0：
       • CHF -> EUR：6.0
       • EUR -> CHF：1 / 6.0 ≈ 0.1667

2. 计算兑换率：

   • 从 initialCurrency（“EUR”）出发，使用 DFS 或 BFS 计算从所有其他货币到 “EUR” 的兑换率（即反向兑换）。
   • 初始化 amount 字典：{"EUR": 1.0}。
   • 从 “EUR” 开始 DFS：
     • “EUR” 可以兑换 “CHF”：amount["CHF"] = amount["EUR"] * (1 / 6.0) ≈ 0.1667。
     • 从 “CHF” 可以兑换 “USD”：amount["USD"] = amount["CHF"] * 0.2 ≈ 0.0333。
     • 从 “USD” 可以兑换 “JPY”：amount["JPY"] = amount["USD"] * 0.25 ≈ 0.0083。
   • 但我们需要的是从其他货币到 “EUR” 的兑换率，因此可以反向计算：
     • 例如，JPY -> EUR 的兑换率可以通过 JPY -> USD -> CHF -> EUR：
       • JPY -> USD：4.0
       • USD -> CHF：5.0
       • CHF -> EUR：6.0
       • 总兑换率：4.0 * 5.0 * 6.0 = 120.0，即 1 JPY = 1 / 120.0 EUR。
   • 更直观的方法是计算从所有货币到 “EUR” 的兑换率：
     • amount["EUR"] = 1.0。
     • amount["CHF"] = 1 / 6.0 ≈ 0.1667（因为 CHF -> EUR：6.0）。
     • amount["USD"] = amount["CHF"] * (1 / 5.0) ≈ 0.0333（因为 USD -> CHF：5.0）。
     • amount["JPY"] = amount["USD"] * (1 / 4.0) ≈ 0.0083（因为 JPY -> USD：4.0）。
   • 但我们需要的是从其他货币兑换回 “EUR” 的兑换率，即 1 / amount[currency]：
     • JPY -> EUR：1 / amount["JPY"] ≈ 120.0。
     • USD -> EUR：1 / amount["USD"] ≈ 30.0。
     • CHF -> EUR：1 / amount["CHF"] ≈ 6.0。
     • EUR -> EUR：1.0。
   • 因此，day2Amount：
     • {"EUR": 1.0, "CHF": 6.0, "USD": 30.0, "JPY": 120.0}。

第三步：组合两天的兑换率

• 对于每一种货币 x：
  • 第一天：从 initialCurrency 兑换到 x 的数量为 day1Amount[x]。
  • 第二天：从 x 兑换回 initialCurrency 的数量为 day2Amount[x]。
  • 因此，通过 x 的最终 initialCurrency 数量为 day1Amount[x] * day2Amount[x]。
• 计算：
  • EUR：1.0 * 1.0 = 1.0。
  • USD：2.0 * 30.0 = 60.0。
  • JPY：6.0 * 120.0 = 720.0。
  • CHF：day1Amount 中没有 “CHF”，因此不考虑。
• 最大值为 720.0。

时间复杂度和空间复杂度

• 时间复杂度：
  • 构建图：O(n + m)，其中 n 是 pairs1 的长度，m 是 pairs2 的长度。
  • DFS/BFS：O(n + m)，因为每个节点和边只访问一次。
  • 因此，总时间复杂度为 O(n + m)。
• 空间复杂度：
  • 存储图：O(n + m)。
  • 存储 amount：O(k)，其中 k 是货币种类的数量（最多 2n 或 2m）。
  • 因此，总空间复杂度为 O(n + m)。

总结

通过构建两天的兑换图并分别计算兑换率，然后组合两天的兑换率，可以找到最大化的初始货币数量。时间复杂度和空间复杂度均为 O(n + m)。

Go完整代码如下：

.

package main

import (
	"fmt"
)

type pair struct {
	to   string
	rate float64
}

func calcAmount(pairs [][]string, rates []float64, initialCurrency string) map[string]float64 {
	g := map[string][]pair{}
	for i, p := range pairs {
		x, y, r := p[0], p[1], rates[i]
		g[x] = append(g[x], pair{y, r})
		g[y] = append(g[y], pair{x, 1 / r})
	}

	amount := map[string]float64{}
	var dfs func(string, float64)
	dfs = func(x string, curAmount float64) {
		amount[x] = curAmount
		for _, e := range g[x] {
			// 每个节点只需递归一次（重复递归算出来的结果是一样的，因为题目保证汇率没有矛盾）
			if amount[e.to] == 0 {
				dfs(e.to, curAmount*e.rate)
			}
		}
	}
	dfs(initialCurrency, 1)
	return amount
}

func maxAmount(initialCurrency string, pairs1 [][]string, rates1 []float64, pairs2 [][]string, rates2 []float64) (ans float64) {
	day1Amount := calcAmount(pairs1, rates1, initialCurrency)
	day2Amount := calcAmount(pairs2, rates2, initialCurrency)
	for x, a2 := range day2Amount {
		ans = max(ans, day1Amount[x]/a2)
	}
	return
}

func main() {
	initialCurrency := "EUR"
	pairs1 := [][]string{{"EUR", "USD"}, {"USD", "JPY"}}
	rates1 := []float64{2.0, 3.0}
	pairs2 := [][]string{{"JPY", "USD"}, {"USD", "CHF"}, {"CHF", "EUR"}}
	rates2 := []float64{4.0, 5.0, 6.0}
	result := maxAmount(initialCurrency, pairs1, rates1, pairs2, rates2)
	fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

from collections import defaultdict

def calc_amount(pairs, rates, initial_currency):
    g = defaultdict(list)
    for (start, end), rate in zip(pairs, rates):
        g[start].append((end, rate))
        g[end].append((start, 1 / rate))

    amount = {}

    def dfs(currency, cur_amount):
        if currency in amount:
            return
        amount[currency] = cur_amount
        for nxt, rate in g[currency]:
            if nxt not in amount:
                dfs(nxt, cur_amount * rate)

    dfs(initial_currency, 1)
    return amount

def max_amount(initial_currency, pairs1, rates1, pairs2, rates2):
    day1_amount = calc_amount(pairs1, rates1, initial_currency)
    day2_amount = calc_amount(pairs2, rates2, initial_currency)
    ans = 0
    for c, a2 in day2_amount.items():
        a1 = day1_amount.get(c, 0)
        if a2 > 0:  # 防止除零
            ans = max(ans, a1 / a2)
    return ans

if __name__ == '__main__':
    initial_currency = "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]
    result = max_amount(initial_currency, pairs1, rates1, pairs2, rates2)
    print(result)