如何解决具有传递性dependencies/graphs的算法题？

Question

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

例如：

假设我得到了一个货币对象列表，其中包含不同的转换率（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;
}

Answer 1

在你提到的问题中，图是有向图。假设您使用邻接矩阵表示图形。用您拥有的所有货币数据填充矩阵。例如，USD->INR 的汇率为 R1，因此 INR->USD 的汇率为 1/R1。填充邻接矩阵后，使用algorithms to compute transitive closure of a directed graph, for example Floyd–Warshall algorithm.

Answer 2

我不确定如何使用 Floyd-Warshall 算法来解决这个问题。但是，我能够使用动态编程解决这个问题。这是我的解决方案：

class Currency{

    String fromCurrency;
    String toCurrency;
    double rate;

    public Currency(String fromCurrency, String toCurrency, double rate) {
        this.fromCurrency = fromCurrency;
        this.toCurrency = toCurrency;
        this.rate = rate;
    }
}

public class CurrencyConverter {

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

        Set<String> currencyNotes = new LinkedHashSet<>();

        for(Currency currency : currencies) {
            currencyNotes.add(currency.fromCurrency);
            currencyNotes.add(currency.toCurrency);
        }

        Map<String, Integer> currencyMap = new TreeMap<>();
        int idx = 0;

        for(String currencyNote : currencyNotes) {
            currencyMap.putIfAbsent(currencyNote, idx++);
        }

        double[][] dp = new double[currencyNotes.size()][currencyNotes.size()];

        for(double[] d : dp) {
            Arrays.fill(d, -1.0);
        }

        for(int i=0;i<currencyNotes.size();i++) {
            dp[i][i] = 1;
        }

        for(Currency currency : currencies) {
            Integer fromCurrencyValue = currencyMap.get(currency.fromCurrency);
            Integer toCurrencyValue = currencyMap.get(currency.toCurrency);

            dp[fromCurrencyValue][toCurrencyValue] = currency.rate;
            dp[toCurrencyValue][fromCurrencyValue] = 1/(currency.rate);
        }

        for(int i=currencyNotes.size()-2;i>=0;i--) {
            for(int j= i+1;j<currencyNotes.size();j++) {
                dp[i][j] = dp[i][j-1]*dp[i+1][j]/(dp[i+1][j-1]);
                dp[j][i] = 1/dp[i][j];
            }
        }

        return dp[currencyMap.get(fromCurrency)][currencyMap.get(toCurrency)];

    }

我认为解决传递依赖问题的最好方法是首先识别节点及其关系，然后回溯。正如黑暗骑士的小丑所说 "Sometimes all it takes is a little push" :)

如何解决具有传递性dependencies/graphs的算法题？

How to solve algorithmic questions with transitive dependencies/graphs?

algorithm

data-structures

graph

transitive-dependency