优秀的响应式网站模板,好看的html,wordpress 自定义帖子,工业设计公司招聘Leetcode 3387. Maximize Amount After Two Days of Conversions 1. 解题思路2. 代码实现 题目链接#xff1a;3387. Maximize Amount After Two Days of Conversions
1. 解题思路
这一题思路上其实就是要分别求出day 1以及day 2中原始货币与其他各个货币之间的成交价…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。
