• Leetcode 3387. Maximize Amount After Two Days of Conversions
  • 1. 解題思路
  • 2. 代碼實現(xiàn)

• 題目鏈接：3387. Maximize Amount After Two Days of Conversions

1. 解題思路

這一題思路上其實就是要分別求出day 1以及day 2中原始貨幣與其他各個貨幣之間的成交價，然后考察一次來回交易所能帶來的最大值。

而對于任意一天，要求指定貨幣與其他所有貨幣的交易價，事實上就是先構建一棵樹，然后遍歷一下樹的全部節(jié)點即可。

2. 代碼實現(xiàn)

給出python代碼實現(xiàn)如下：

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，占用內(nèi)存17.4MB。