leetcode 399. Evaluate Division | 399. 除法求值（图的邻接表，DFS）

深碍√TFBOYSˉ_ 2022-09-02 04:26 152阅读 0赞

## 题目 ##

[https://leetcode.com/problems/evaluate-division/][https_leetcode.com_problems_evaluate-division]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

题目看着复杂，实际上是图的 DFS。

例如，已知 a/b, b/c, c/d，想求 a/d 的话，得到路径就是 a->b->c->d。

根据乘除法的性质，将路过的所有数相乘即可。为了方便将路过的所有数字相乘，我们初始化一个`k:k:v` 形式的 map，其含义是 `from:to:distance`。

由于本题的背景是连等式，所以全局只有一条可行路径，在 DFS 的过程中，只要发现了可行路径，直接一把梭返回。

附上潦草的草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { 
            // init
            Map<String, List<String>> G = new HashMap<>();
            Map<String, Map<String, Double>> kkv = new HashMap<>();
            for (int i = 0; i < equations.size(); i++) { 
                List<String> pair = equations.get(i);
                // init distance map
                if (!kkv.containsKey(pair.get(0))) kkv.put(pair.get(0), new HashMap<>());
                kkv.get(pair.get(0)).put(pair.get(1), values[i]);
                if (!kkv.containsKey(pair.get(1))) kkv.put(pair.get(1), new HashMap<>());
                kkv.get(pair.get(1)).put(pair.get(0), 1.0 / values[i]);
                // init adjacent list
                if (!G.containsKey(pair.get(0))) G.put(pair.get(0), new ArrayList<>());
                if (!G.containsKey(pair.get(1))) G.put(pair.get(1), new ArrayList<>());
                G.get(pair.get(0)).add(pair.get(1));
                G.get(pair.get(1)).add(pair.get(0));
            }
            // dfs
            double[] res = new double[queries.size()];
            int p = 0;
            for (List<String> pair : queries) { 
                Double dfs = dfs(G, kkv, new HashSet<>(), pair.get(0), pair.get(1), 1.0);
                res[p++] = dfs == null ? -1 : dfs;
            }
            return res;
        }
    
        // 全局仅有一条可行路径。故，只要发现一条可行，直接返回即可
        public Double dfs(Map<String, List<String>> G, Map<String, Map<String, Double>> kkv, Set<String> visited, String from, String to, Double distance) { 
            if (!G.containsKey(from) || !G.containsKey(to)) return null;
            if (from.equals(to)) return distance;
    
            for (String next : G.get(from)) { 
                if (!visited.contains(next)) { 
                    if (kkv.containsKey(from) && kkv.get(from).containsKey(next)) { 
                        visited.add(next);
                        Double res = dfs(G, kkv, visited, next, to, distance * kkv.get(from).get(next));
                        visited.remove(next);
                        if (res != null) return res;
                    }
                }
            }
            return null;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_evaluate-division]: https://leetcode.com/problems/evaluate-division/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/8a19c94ff86248ad8808c2f9a40718c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/5c20dc8d069745e9bb65d8152864c930.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/0be9efcdf27c483995ab7c30f6b2647d.png