Leetcode 3387. Maximize Amount After Two Days of Conversions

• Leetcode 3387. Maximize Amount After Two Days of Conversions
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3387. Maximize Amount After Two Days of Conversions

1. 解题思路

这一题思路上其实就是要分别求出day 1以及day 2中原始货币与其他各个货币之间的成交价，然后考察一次来回交易所能带来的最大值。

而对于任意一天，要求指定货币与其他所有货币的交易价，事实上就是先构建一棵树，然后遍历一下树的全部节点即可。

2. 代码实现

给出python代码实现如下：

class Solution:def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float:def get_rate(pairs, rates, currency):graph = defaultdict(list)for (u, v), r in zip(pairs, rates):graph[u].append((v, r))graph[v].append((u, 1/r))ans = {}q = [(currency, 1.0)]while q:u, r = q.pop(0)ans[u] = rfor v, r in graph[u]:if v in ans:continueq.append((v, ans[u] * r))return ansday1_rate = get_rate(pairs1, rates1, initialCurrency)day2_rate = get_rate(pairs2, rates2, initialCurrency)ans = 1for currency in day2_rate:ans = max(ans, day1_rate.get(currency, 0.0) / day2_rate.get(currency, 0.0))return ans

提交代码评测得到：耗时7ms，占用内存17.4MB。