国外外贸需求网站,响应式布局网页,做qq空间网站,wordpress兼容html5一、题目
给你一个变量对数组equations和一个实数值数组values作为已知条件#xff0c;其中equations[i] [Ai, Bi]和values[i]共同表示等式Ai / Bi values[i]。每个Ai或Bi是一个表示单个变量的字符串。另有一些以数组queries表示的问题#xff0c;其中queries[j] [Cj, Dj…一、题目
给你一个变量对数组equations和一个实数值数组values作为已知条件其中equations[i] [Ai, Bi]和values[i]共同表示等式Ai / Bi values[i]。每个Ai或Bi是一个表示单个变量的字符串。另有一些以数组queries表示的问题其中queries[j] [Cj, Dj]表示第j个问题请你根据已知条件找出Cj / Dj ?的结果作为答案。返回 所有问题的答案 。如果存在某个无法确定的答案则用-1.0替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串也需要用-1.0替代这个答案。
注意输入总是有效的。你可以假设除法运算中不会出现除数为0的情况且不存在任何矛盾的结果。
注意未在等式列表中出现的变量是未定义的因此无法确定它们的答案。
示例 1
输入equations [[a,b],[b,c]], values [2.0,3.0], queries [[a,c],[b,a],[a,e],[a,a],[x,x]] 输出[6.00000,0.50000,-1.00000,1.00000,-1.00000] 解释 条件a / b 2.0, b / c 3.0 问题a / c ?, b / a ?, a / e ?, a / a ?, x / x ? 结果[6.0, 0.5, -1.0, 1.0, -1.0 ] 注意x是未定义的 -1.0
示例 2
输入equations [[a,b],[b,c],[bc,cd]], values [1.5,2.5,5.0], queries [[a,c],[c,b],[bc,cd],[cd,bc]] 输出[3.75000,0.40000,5.00000,0.20000]
示例 3
输入equations [[a,b]], values [0.5], queries [[a,b],[b,a],[a,c],[x,y]] 输出[0.50000,2.00000,-1.00000,-1.00000] 1 equations.length 20 equations[i].length 2 1 Ai.length, Bi.length 5 values.length equations.length 0.0 values[i] 20.0 1 queries.length 20 queries[i].length 2 1 Cj.length, Dj.length 5 Ai,Bi,Cj,Dj由小写英文字母与数字组成 二、代码
广度优先搜索 我们可以将整个问题建模成一张图给定图中的一些点变量以及某些边的权值两个变量的比值试对任意两点两个变量求出其路径长两个变量的比值。因此我们首先需要遍历equations数组找出其中所有不同的字符串并通过哈希表将每个不同的字符串映射成整数。
在构建完图之后对于任何一个查询就可以从起点出发通过广度优先搜索的方式不断更新起点与当前点之间的路径长度直到搜索到终点为止。
class Solution {public double[] calcEquation(ListListString equations, double[] values, ListListString queries) {int nvars 0;MapString, Integer variables new HashMapString, Integer();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();}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;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];Arrays.fill(ratios, -1.0);ratios[ia] 1.0;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;}
}时间复杂度 O(MLQ⋅(LM))其中M为边的数量Q为询问的数量L为字符串的平均长度。构建图时需要处理M条边每条边都涉及到O(L)的字符串比较处理查询时每次查询首先要进行一次O(L)的比较然后至多遍历O(M)条边。 空间复杂度 O(NLM)其中N为点的数量M为边的数量L为字符串的平均长度。为了将每个字符串映射到整数需要开辟空间为O(NL)的哈希表随后需要花费O(M)的空间存储每条边的权重处理查询时还需要O(N)的空间维护访问队列。最终总的复杂度为O(NLMN)O(NLM)。
【2】Floyd 算法 对于查询数量很多的情形如果为每次查询都独立搜索一次则效率会变低。为此我们不妨对图先做一定的预处理随后就可以在较短的时间内回答每个查询。在本题中我们可以使用Floyd算法预先计算出任意两点之间的距离。
class Solution {public double[] calcEquation(ListListString equations, double[] values, ListListString queries) {int nvars 0;MapString, Integer variables new HashMapString, Integer();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);}}double[][] graph new double[nvars][nvars];for (int i 0; i nvars; i) {Arrays.fill(graph[i], -1.0);}for (int i 0; i n; i) {int va variables.get(equations.get(i).get(0)), vb variables.get(equations.get(i).get(1));graph[va][vb] values[i];graph[vb][va] 1.0 / values[i];}for (int k 0; k nvars; k) {for (int i 0; i nvars; i) {for (int j 0; j nvars; j) {if (graph[i][k] 0 graph[k][j] 0) {graph[i][j] graph[i][k] * graph[k][j];}}}}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;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 (graph[ia][ib] 0) {result graph[ia][ib];}}ret[i] result;}return ret;}
}时间复杂度 O(MLN3QL)。构建图需要O(ML)的时间Floyd算法需要O(N^3)的时间处理查询时单次查询只需要O(L)的字符串比较以及常数时间的额外操作。 空间复杂度 O(NLN^2)。
