algorithm - 如何解决具有传递依赖关系/图的算法问题？

Question

当我在面试中被问到这些问题时，我有点挣扎。举例来说，我有一个问题，我需要找到从一种货币转换为另一种货币的货币金额，并且我得到了货币列表。如何构建邻接/关系映射，以便获得正确的数量。即使是解释逻辑的算法也足够了。感谢您对此的建议！

例如：

假设我得到了一个包含不同兑换率（USD->INR = 75，INR -> XXX = 100）的货币对象列表。我需要找到从 USD-> XXX = 7500 的转换。我还应该能够进行反向转换，比如 INR->USD。如何通过构建图表找到它？

public Currency{
String fromCurrency;
String toCurrency;
double rate;
}

public double currencyConverter(List<Currency> currencies, fromCurrency, toCurrency){

return convertedCurrency;
}

标签： algorithmdata-structuresgraphtransitive-dependency

Answer 1

在您提到的问题中，图是有向图。假设您使用邻接矩阵表示图。用所有货币的数据填充矩阵。例如，USD->INR 有R1汇率，因此 INR->USD 将是 1/R1汇率。填充邻接矩阵后，使用算法计算有向图的传递闭包，例如Floyd-Warshall 算法。