You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Example 1:
Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000] Explanation: Given: a / b = 2.0, b / c = 3.0 queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
Example 2:
Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output: [3.75000,0.40000,5.00000,0.20000]
Example 3:
Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output: [0.50000,2.00000,-1.00000,-1.00000]
Constraints:
1 <= equations.length <= 20equations[i].length == 21 <= Ai.length, Bi.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= Cj.length, Dj.length <= 5-
Ai, Bi, Cj, Djconsist of lower case English letters and digits.
除法求值。
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路是DFS。
这是一道图论的题目。equations里面的每一对字母组合 [a, b] 代表 a / b，结果在 values 数组对应的index下。我们可以把这个算式理解为图中从点A到点B，向量的值为 values[index]，同时，图中从点B到点A，向量的值为 1.0 / values[index]。我们可以利用这些信息把图先建立起来，接着用DFS，遍历的时候，用一个变量temp记录中间结果。中间结果的意思是比如在图中你从A点出发只能到B点（B是A的邻居节点但是C不是），从B点出发只能到C点的话，那么我们需要先用一个变量把从A到B的向量值记录下来，才能继续之后的递归。
时间O(V + E)
空间O(n)
Java实现
1 class Solution {
2 public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
3 HashMap<String, HashMap<String, Double>> g = new HashMap<>();
4 buildGraph(g, equations, values);
5 double[] res = new double[queries.size()];
6 // 默认值是-1，表示找不到对应的计算结果
7 Arrays.fill(res, -1.0);
8 // 表示处理到第几个query了
9 int index = 0;
10 for (List<String> q : queries) {
11 String a = q.get(0);
12 String b = q.get(1);
13 if (!g.containsKey(a) || !g.containsKey(b)) {
14 index++;
15 continue;
16 } else {
17 dfs(g, a, b, res, index, new HashSet<>(), 1.0);
18 index++;
19 }
20 }
21 return res;
22 }
23
24 private void buildGraph(HashMap<String, HashMap<String, Double>> g, List<List<String>> equations, double[] values) {
25 int index = 0;
26 for (List<String> e : equations) {
27 String a = e.get(0);
28 String b = e.get(1);
29 g.putIfAbsent(a, new HashMap<>());
30 g.putIfAbsent(b, new HashMap<>());
31 // 记录a / b
32 g.get(a).put(b, values[index]);
33 // 记录 b / a
34 g.get(b).put(a, 1.0 / values[index]);
35 index++;
36 // a / a和b / b都是1
37 g.get(a).put(a, 1.0);
38 g.get(b).put(b, 1.0);
39 }
40 }
41
42 // visited表示访问过哪些节点
43 // temp表示中间的计算结果
44 private void dfs(HashMap<String, HashMap<String, Double>> g, String a, String b, double[] res, int index,
45 HashSet<String> visited, double temp) {
46 visited.add(a);
47 if (g.get(a) == null || g.get(a).size() == 0) {
48 return;
49 }
50 if (g.get(a).containsKey(b)) {
51 res[index] = g.get(a).get(b) * temp;
52 return;
53 }
54 for (String next : g.get(a).keySet()) {
55 if (visited.contains(next)) {
56 continue;
57 }
58 dfs(g, next, b, res, index, visited, g.get(a).get(next) * temp);
59 }
60 }
61 }