type
status
date
slug
summary
tags
category
icon
password
创建时间
Jan 2, 2025 02:54 AM
给你一个字符串
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.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 * 1010。
深度优先遍历——层次图（两个图在一个图中）
这个题做的优点难受，题目太长了，还读不太懂。5555
注意：最长路径与最短路径，不能直接相互套用。求最长路径，只能暴力 DFS 递归。
参考 灵茶山艾府 的 b 站讲解视频。构造有向无环图，不需要
visted 数组。将两天的数组建立在一个图上，使用一次 dfs 就可以将答案输出出来。在建图的时候，还是双向边，怎么保证不走循环路（A→B→A）呢？
- 使用
visited数组来标记——常用
- 引入另一个变量，标记从哪个点过来，判断当前的点邻居的邻居是否为来时的点即可，不会出现死循环（仅仅适合本题）
- 出现这种环不能使用这种方法
