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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。