P190 除法求值

描述#

这个题目说的是，给你一系列形如 A / B = K 的等式，其中 A 和 B 是字符串，K 是浮点数。你要根据这些等式，为一系列的除法表达式求值。如果求值结果不存在，就返回 -1.0。

注意，假设给你的输入总是有效的。也就是说你不需要考虑除 0 或者输入中存在其他问题的情况。

比如说，给你 3 个等式：
a / b = 2.0
b / c = 4.0
c / d = 5.0
这三个等式，以两个序列的形式提供给你：
[["a", "b"], ["b", "c"], ["c", "d"]]
[2.0, 4.0, 5.0]
另外，题目还提供了一个查询序列，表示一系列除法：
[["a","d"], ["b","a"], ["a","c"], ["a","e"], ["a","a"], ["e","e"]]
根据前面提供的 3 个等式，计算出查询序列的结果并返回：
[40, 0.5, 8, -1, 1, -1]

代码#

public class AlgoCasts {

  private Double dfs(String cur, String end, double result,
                     Set<String> visited,
                     Map<String, Map<String, Double>> graph) {
    Map<String, Double> nexts = graph.get(cur);
    if (nexts.containsKey(end)) return result * nexts.get(end);
    for (Map.Entry<String, Double> next: nexts.entrySet()) {
      if (visited.contains(next.getKey())) continue;
      visited.add(next.getKey());
      Double ret = dfs(next.getKey(), end, result * next.getValue(), visited, graph);
      if (ret != null) return ret;
    }
    return null;
  }

  // Time: O(m*V), Space: O(V+E)
  public double[] calcEquation(List<List<String>> equations, double[] values,
                               List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = new HashMap<>();
    for (int i = 0; i < equations.size(); ++i) {
      String a = equations.get(i).get(0);
      String b = equations.get(i).get(1);
      if (!graph.containsKey(a)) graph.put(a, new HashMap<>());
      graph.get(a).put(b, values[i]);
      if (!graph.containsKey(b)) graph.put(b, new HashMap<>());
      graph.get(b).put(a, 1 / values[i]);
    }

    double[] result = new double[queries.size()];
    for (int i = 0; i < queries.size(); ++i) {
      String a = queries.get(i).get(0);
      String b = queries.get(i).get(1);
      if (!graph.containsKey(a) || !graph.containsKey(b)) {
        result[i] = -1.0;
      } else if (a.equals(b)) {
        result[i] = 1.0;
      } else {
        Double ret = dfs(a, b, 1.0, new HashSet<>(), graph);
        result[i] = ret != null ? ret : -1.0;
      }
    }
    return result;
  }

}