LeetCode399——除法求值

Myth丶恋晨 2022-01-22 07:31 248阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[https://leetcode-cn.com/problems/evaluate-division/][https_leetcode-cn.com_problems_evaluate-division]

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：图的深度优先遍历

### 思路：图的深度优先遍历 ###

本题是一题经典的图论算法，这里的除法运算可以看成是连接两个节点的一条有向边，那么计算结果存在的条件是什么呢？

（1）**两个字符串在equations中都出现过**。

（2）**这两个字符串在equations中存在联系，即同属于一个连通分量**。

首先，**利用一个Map将字符串与数字编号一一对应起来**。

对于图的深度优先遍历，我们选择用一个邻接矩阵graph来存储图的边权值，同时每一次求两点间的距离都初始化一个visited数组来标记哪些节点已经被遍历过。深度优先遍历过程中，求解距离用的不应该是加法，而应该是**乘法**。

时间复杂度是O(n \* m)，其中n为queries中的查询数，而m指的是由equations生成的节点数。空间复杂度是O(m ^ 2)。

JAVA代码：

public class Solution {
    
        private Map<String, Integer> stringToInteger = new HashMap<>();
    
        private int index = 0;
    
        private double[][] graph;
    
        private boolean[] visited;
    
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            for (List<String> list : equations) {
                for (String string : list) {
                    if (!stringToInteger.containsKey(string)) {
                        stringToInteger.put(string, index++);
                    }
                }
            }
            graph = new double[index][index];
            for (int i = 0; i < equations.size(); i++) {
                List<String> list = equations.get(i);
                String string0 = list.get(0), string1 = list.get(1);
                int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
                graph[index1][index2] = values[i];
                graph[index2][index1] = 1.0 / values[i];
            }
            double[] result = new double[queries.size()];
            Arrays.fill(result, -1.0);
            for (int i = 0; i < result.length; i++) {
                List<String> list = queries.get(i);
                String string0 = list.get(0), string1 = list.get(1);
                if (stringToInteger.containsKey(string0) && stringToInteger.containsKey(string1)) {
                    if (string0.equals(string1)) {
                        result[i] = 1.0;
                    } else {
                        int index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
                        visited = new boolean[index];
                        double len = 1.0;
                        dfs(index1, index2, len, result, i);
                    }
                }
            }
            return result;
        }
    
        private void dfs(int begin, int end, double len, double[] result, int k) {
            if (graph[begin][end] == 0) {
                visited[begin] = true;
                for (int i = 0; i < index; i++) {
                    if (!visited[i] && graph[begin][i] != 0) {
                        dfs(i, end, len * graph[begin][i], result, k);
                    }
                }
            } else {
                result[k] = len * graph[begin][end];
            }
        }
    
    }

LeetCode解题报告：

![20190605161538114.png][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[https_leetcode-cn.com_problems_evaluate-division]: https://leetcode-cn.com/problems/evaluate-division/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220122/02cecbc8787245eebaf949e5af680a51.png
[20190605161538114.png]: /images/20220122/9afe5299361d484c9a90c036c3a7fec5.png