Leetcode 面试150题 399.除法求值

系列博客目录

题目

链接

思路

广度优先搜索

我们可以将整个问题建模成一张图：给定图中的一些点（点即变量），以及某些边的权值（权值即两个变量的比值），试对任意两点（两个变量）求出其路径长（两个变量的比值）。

因此，我们首先需要遍历 equations 数组，找出其中所有不同的字符串(作为图的点)，并通过哈希表将每个不同的字符串映射成整数(方便在代码中进行表示)。

在构建完图之后，对于任何一个查询，就可以从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。比如已知a/b和b/c，我们要求a/c，其实就是找到点a，通过广度优先找到b(通过线段X，其值为a/b)，再从b找到c(通过线段Y，其值为(a/b)*(b/c))。

代码

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nvars = 0;//后面通过nvars不断增加，为字符串变量赋值不同的数字。
        //变量存到HashMap中，实现字符串变量与数字一一对应。
        Map<String, Integer> variables = new HashMap<String, Integer>();
		//找到所有变量，为其指定唯一一个数字，nvars的值变成了变量的数量
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (!variables.containsKey(equations.get(i).get(0))) {
                variables.put(equations.get(i).get(0), nvars++);
            }
            if (!variables.containsKey(equations.get(i).get(1))) {
                variables.put(equations.get(i).get(1), nvars++);
            }
        }

        // 对于每个点，存储其直接连接到的所有点及对应的权值
        List<Pair>[] edges = new List[nvars];
        for (int i = 0; i < nvars; i++) {
            edges[i] = new ArrayList<Pair>();//为每个变量初始化一个链表，链表存放Pair类型的值
        }
        //为每个变量赋值 把与其有关联的变量以及与所关联变量所一一对应的值放入链表
        for (int i = 0; i < n; i++) {
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            edges[va].add(new Pair(vb, values[i]));
            edges[vb].add(new Pair(va, 1.0 / values[i]));
        }

        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];//存储最后结果
        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);//取出一个查询，这个查询包含两部分，两个字符串，我们需要求前字符串除后字符串的值。
            double result = -1.0;//如果之后发现之前存储所有变量的map中没有构成这个查询的两个字符串中的任意一个，直接返回 -1.0，即查询不到结果。
            if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
            	//找到构成查询的两个字符串所变量对应的数字
                int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
                if (ia == ib) {
                    result = 1.0;
                } else {
                	//开始广度优先遍历
                    Queue<Integer> points = new LinkedList<Integer>();
                    points.offer(ia);
                    double[] ratios = new double[nvars];//用来标记查询中第一个字符串变量到达他所能够到达的所有变量后，即其除以这个变量的比值(即可以得到以ia为分子的比值的所有结果)，最后只取出我们需要的那个变量所在位置的值作为答案。
                    Arrays.fill(ratios, -1.0);
                    ratios[ia] = 1.0;//标记自己到自己，且比值为 1 

                    while (!points.isEmpty() && ratios[ib] < 0) {
                        int x = points.poll();
                        for (Pair pair : edges[x]) {
                            int y = pair.index;
                            double val = pair.value;
                            if (ratios[y] < 0) {//判断是否遍历过，避免产生环。
                                ratios[y] = ratios[x] * val;
                                points.offer(y);
                            }
                        }
                    }
                    result = ratios[ib];//取出本次查询的答案
                }
            }
            ret[i] = result;
        }
        return ret;
    }
}

class Pair {
    int index;
    double value;

    Pair(int index, double value) {
        this.index = index;
        this.value = value;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/evaluate-division/solutions/548585/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：力扣官方题解
链接：https://leetcode.cn/problems/evaluate-division/solutions/548585/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。