3387. 两天转换后的最大金额

Medium

题目描述

给你一个字符串 initialCurrency，你开始时拥有 1.0 单位的 initialCurrency。

同时给你四个数组，包含货币对（字符串）和汇率（实数）：

pairs1[i] = [startCurrencyi, targetCurrencyi] 表示在第一天你可以以汇率 rates1[i] 从 startCurrencyi 转换为 targetCurrencyi。
pairs2[i] = [startCurrencyi, targetCurrencyi] 表示在第二天你可以以汇率 rates2[i] 从 startCurrencyi 转换为 targetCurrencyi。
另外，每个 targetCurrency 都可以以汇率 1 / rate 转换回对应的 startCurrency。

你可以在第一天使用 rates1 进行任意次数的转换（包括零次），然后在第二天使用 rates2 进行任意次数的转换（包括零次）。

返回在两天都进行任意次数转换后，你能拥有的 initialCurrency 的最大金额。

示例 1：

输入：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 开始：
第一天：
- 将 EUR 转换为 USD 得到 2.0 USD
- 将 USD 转换为 JPY 得到 6.0 JPY
第二天：
- 将 JPY 转换为 USD 得到 24.0 USD
- 将 USD 转换为 CHF 得到 120.0 CHF
- 最后将 CHF 转换为 EUR 得到 720.0 EUR

示例 2：

输入：initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9.0], pairs2 = [["NGN","EUR"]], rates2 = [6.0]
输出：1.50000

示例 3：

输入：initialCurrency = "USD", pairs1 = [["USD","EUR"]], rates1 = [1.0], pairs2 = [["EUR","JPY"]], rates2 = [10.0]
输出：1.00000

约束条件：

1 <= initialCurrency.length <= 3
1 <= pairs1.length, pairs2.length <= 10
1.0 <= rates1[i], rates2[i] <= 10.0

解题思路

这道题的核心思路是通过选择一个中间货币，在第一天从初始货币转换到中间货币，然后在第二天从中间货币转换回初始货币，从而最大化最终的金额。

算法步骤：

构建图结构：将每天的汇率对构建成有向图，每个货币是节点，汇率是边的权重。注意需要添加反向边（汇率为原汇率的倒数）。
计算最大汇率：使用 BFS 或 DFS 从初始货币出发，计算到每个可达货币的最大汇率。这里使用 BFS 比较直观。
枚举中间货币：对于每个在第一天能到达的货币，计算：
- 第一天从初始货币到该货币的最大汇率
- 第二天从该货币回到初始货币的最大汇率
- 两者相乘得到总收益
返回最大值：在所有可能的路径中选择收益最大的那个。

关键优化：

使用 unordered_map 存储图结构，便于快速查找
BFS 中使用优先队列确保优先探索汇率更高的路径
记忆化搜索避免重复计算

时间复杂度主要取决于 BFS 的执行，由于货币种类和转换对都很少，整体复杂度是可控的。

代码实现

class Solution {
public:
    double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
        auto buildGraph = [](const vector<vector<string>>& pairs, const vector<double>& rates) {
            unordered_map<string, vector<pair<string, double>>> graph;
            for (int i = 0; i < pairs.size(); i++) {
                graph[pairs[i][0]].push_back({pairs[i][1], rates[i]});
                graph[pairs[i][1]].push_back({pairs[i][0], 1.0 / rates[i]});
            }
            return graph;
        };
        
        auto getMaxRate = [](const unordered_map<string, vector<pair<string, double>>>& graph, const string& start) {
            unordered_map<string, double> maxRate;
            priority_queue<pair<double, string>> pq;
            pq.push({1.0, start});
            maxRate[start] = 1.0;
            
            while (!pq.empty()) {
                auto [rate, curr] = pq.top();
                pq.pop();
                
                if (rate < maxRate[curr]) continue;
                
                if (graph.find(curr) != graph.end()) {
                    for (auto [next, nextRate] : graph.at(curr)) {
                        double newRate = rate * nextRate;
                        if (maxRate.find(next) == maxRate.end() || newRate > maxRate[next]) {
                            maxRate[next] = newRate;
                            pq.push({newRate, next});
                        }
                    }
                }
            }
            return maxRate;
        };
        
        auto graph1 = buildGraph(pairs1, rates1);
        auto graph2 = buildGraph(pairs2, rates2);
        
        auto day1Rates = getMaxRate(graph1, initialCurrency);
        
        double maxResult = 1.0;  // 不进行任何转换的情况
        
        for (auto [currency, rate1] : day1Rates) {
            auto day2Rates = getMaxRate(graph2, currency);
            if (day2Rates.find(initialCurrency) != day2Rates.end()) {
                maxResult = max(maxResult, rate1 * day2Rates[initialCurrency]);
            }
        }
        
        return maxResult;
    }
};

class Solution:
    def maxAmount(self, initialCurrency: str, pairs1: List[List[str]], rates1: List[float], pairs2: List[List[str]], rates2: List[float]) -> float:
        from collections import defaultdict
        import heapq
        
        def build_graph(pairs, rates):
            graph = defaultdict(list)
            for i, (start, target) in enumerate(pairs):
                graph[start].append((target, rates[i]))
                graph[target].append((start, 1.0 / rates[i]))
            return graph
        
        def get_max_rate(graph, start):
            max_rate = {start: 1.0}
            pq = [(-1.0, start)]  # 使用负值因为heapq是最小堆
            
            while pq:
                neg_rate, curr = heapq.heappop(pq)
                rate = -neg_rate
                
                if rate < max_rate.get(curr, 0):
                    continue
                
                for next_curr, next_rate in graph[curr]:
                    new_rate = rate * next_rate
                    if next_curr not in max_rate or new_rate > max_rate[next_curr]:
                        max_rate[next_curr] = new_rate
                        heapq.heappush(pq, (-new_rate, next_curr))
            
            return max_rate
        
        graph1 = build_graph(pairs1, rates1)
        graph2 = build_graph(pairs2, rates2)
        
        day1_rates = get_max_rate(graph1, initialCurrency)
        
        max_result = 1.0  # 不进行任何转换的情况
        
        for currency, rate1 in day1_rates.items():
            day2_rates = get_max_rate(graph2, currency)
            if initialCurrency in day2_rates:
                max_result = max(max_result, rate1 * day2_rates[initialCurrency])
        
        return max_result

public class Solution {
    public double MaxAmount(string initialCurrency, IList<IList<string>> pairs1, double[] rates1, IList<IList<string>> pairs2, double[] rates2) {
        var buildGraph = new Func<IList<IList<string>>, double[], Dictionary<string, List<(string, double)>>>((pairs, rates) => {
            var graph = new Dictionary<string, List<(string, double)>>();
            for (int i = 0; i < pairs.Count; i++) {
                if (!graph.ContainsKey(pairs[i][0])) graph[pairs[i][0]] = new List<(string, double)>();
                if (!graph.ContainsKey(pairs[i][1])) graph[pairs[i][1]] = new List<(string, double)>();
                
                graph[pairs[i][0]].Add((pairs[i][1], rates[i]));
                graph[pairs[i][1]].Add((pairs[i][0], 1.0 / rates[i]));
            }
            return graph;
        });
        
        var getMaxRate = new Func<Dictionary<string, List<(string, double)>>, string, Dictionary<string, double>>((graph, start) => {
            var maxRate = new Dictionary<string, double> { [start] = 1.0 };
            var pq = new PriorityQueue<(double, string), double>();
            pq.Enqueue((1.0, start), -1.0);
            
            while (pq.Count > 0) {
                var (rate, curr) = pq.Dequeue();
                
                if (rate < maxRate.GetValueOrDefault(curr, 0)) continue;
                
                if (graph.ContainsKey(curr)) {
                    foreach (var (next, nextRate) in graph[curr]) {
                        double newRate = rate * nextRate;
                        if (!maxRate.ContainsKey(next) || newRate > maxRate[next]) {
                            maxRate[next] = newRate;
                            pq.Enqueue((newRate, next), -newRate);
                        }
                    }
                }
            }
            return maxRate;
        });
        
        var graph1 = buildGraph(pairs1, rates1);
        var graph2 = buildGraph(pairs2, rates2);
        
        var day1Rates = getMaxRate(graph1, initialCurrency);
        
        double maxResult = 1.0;
        
        foreach (var (currency, rate1) in day1Rates) {
            var day2Rates = getMaxRate(graph2, currency);
            if (day2Rates.ContainsKey(initialCurrency)) {
                maxResult = Math.Max(maxResult, rate1 * day2Rates[initialCurrency]);
            }
        }
        
        return maxResult;
    }
}

var maxAmount = function(initialCurrency, pairs1, rates1, pairs2, rates2) {
    const buildGraph = (pairs, rates) => {
        const graph = new Map();
        for (let i = 0; i < pairs.length; i++) {
            if (!graph.has(pairs[i][0])) graph.set(pairs[i][0], []);
            if (!graph.has(pairs[i][1])) graph.set(pairs[i][1], []);
            
            graph.get(pairs[i][0]).push([pairs[i][1], rates[i]]);
            graph.get(pairs[i][1]).push([pairs[i][0], 1.0 / rates[i]]);
        }
        return graph;
    };
    
    const getMaxRate = (graph, start) => {
        const maxRate = new Map([[start, 1.0]]);
        const pq = [[1.0, start]];
        
        while (pq.length > 0) {
            pq.sort((a, b) => b[0] - a[0]);
            const [rate, curr] = pq.shift();
            
            if (rate < (maxRate.get(curr) || 0)) continue;
            
            if (graph.has(curr)) {
                for (const [next, nextRate] of graph.get(curr)) {
                    const newRate = rate * nextRate;
                    if (!maxRate.has(next) || newRate > maxRate.get(next)) {
                        maxRate.set(next, newRate);
                        pq.push([newRate, next]);
                    }
                }
            }
        }
        return maxRate;
    };
    
    const graph1 = buildGraph(pairs1, rates1);
    const graph2 = buildGraph(pairs2, rates2);
    
    const day1Rates = getMaxRate(graph1, initialCurrency);
    
    let maxResult = 1.0;
    
    for (const [currency, rate1] of day1Rates) {
        const day2Rates = getMaxRate(graph2, currency);
        if (day2Rates.has(initialCurrency)) {
            maxResult = Math.max(maxResult, rate1 * day2Rates.get(initialCurrency));
        }
    }
    
    return maxResult;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间复杂度	O(N²logN)
空间复杂度	O(N²)

其中 N 是货币种类的总数。时间复杂度来自于对每个货币都需要执行一次 BFS，每次 BFS 的复杂度是 O(NlogN)。空间复杂度主要用于存储图结构和汇率映射表。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目