自己服务器建网站 备案,双井做网站的公司,如何增加百度收录,龙华做网站多少钱系列博客目录 文章目录 系列博客目录题目思路代码 题目
链接
思路
广度优先搜索
我们可以将整个问题建模成一张图#xff1a;给定图中的一些点#xff08;点即变量#xff09;#xff0c;以及某些边的权值#xff08;权值即两个变量的比值#xff09;#xff0c;试…系列博客目录 文章目录 系列博客目录题目思路代码 题目
链接
思路
广度优先搜索
我们可以将整个问题建模成一张图给定图中的一些点点即变量以及某些边的权值权值即两个变量的比值试对任意两点两个变量求出其路径长两个变量的比值。
因此我们首先需要遍历 equations 数组找出其中所有不同的字符串(作为图的点)并通过哈希表将每个不同的字符串映射成整数(方便在代码中进行表示)。
在构建完图之后对于任何一个查询就可以从起点出发通过广度优先搜索的方式不断更新起点与当前点之间的路径长度直到搜索到终点为止。比如已知a/b和b/c我们要求a/c其实就是找到点a通过广度优先找到b(通过线段X其值为a/b)再从b找到c(通过线段Y其值为(a/b)*(b/c))。
代码
class Solution {public double[] calcEquation(ListListString equations, double[] values, ListListString queries) {int nvars 0;//后面通过nvars不断增加为字符串变量赋值不同的数字。//变量存到HashMap中实现字符串变量与数字一一对应。MapString, Integer variables new HashMapString, 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);}}// 对于每个点存储其直接连接到的所有点及对应的权值ListPair[] edges new List[nvars];for (int i 0; i nvars; i) {edges[i] new ArrayListPair();//为每个变量初始化一个链表链表存放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) {ListString 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 {//开始广度优先遍历QueueInteger points new LinkedListInteger();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 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
