|
30 | 30 | */ |
31 | 31 | publicclass_399 { |
32 | 32 |
|
33 | | -/**Credit: https://discuss.leetcode.com/topic/59146/java-ac-solution-using-graph |
34 | | - * |
35 | | - * Image a/b = k as a link between node a and b, the weight from a to b is k, the reverse link is 1/k. Query is to find a path between two nodes.*/ |
36 | | -publicdouble[]calcEquation(String[][]equations,double[]values,String[][]queries) { |
37 | | -Map<String,List<String>>pairs =newHashMap<>(); |
38 | | -Map<String,List<Double>>valuePairs =newHashMap<>(); |
39 | | -for (inti =0;i <equations.length;i++) { |
40 | | -String[]equation =equations[i]; |
41 | | -if (!pairs.containsKey(equation[0])) { |
42 | | -pairs.put(equation[0],newArrayList<>()); |
43 | | -valuePairs.put(equation[0],newArrayList<>()); |
| 33 | +publicstaticclassSolution1 { |
| 34 | +/** |
| 35 | + * Credit: https://discuss.leetcode.com/topic/59146/java-ac-solution-using-graph |
| 36 | + * |
| 37 | + * Image a/b = k as a link between node a and b, the weight from a to b is k, the reverse link |
| 38 | + * is 1/k. Query is to find a path between two nodes. |
| 39 | + */ |
| 40 | +publicdouble[]calcEquation(String[][]equations,double[]values,String[][]queries) { |
| 41 | +Map<String,List<String>>pairs =newHashMap<>(); |
| 42 | +Map<String,List<Double>>valuePairs =newHashMap<>(); |
| 43 | +for (inti =0;i <equations.length;i++) { |
| 44 | +String[]equation =equations[i]; |
| 45 | +if (!pairs.containsKey(equation[0])) { |
| 46 | +pairs.put(equation[0],newArrayList<>()); |
| 47 | +valuePairs.put(equation[0],newArrayList<>()); |
| 48 | + } |
| 49 | +if (!pairs.containsKey(equation[1])) { |
| 50 | +pairs.put(equation[1],newArrayList<>()); |
| 51 | +valuePairs.put(equation[1],newArrayList<>()); |
| 52 | + } |
| 53 | +pairs.get(equation[0]).add(equation[1]); |
| 54 | +pairs.get(equation[1]).add(equation[0]); |
| 55 | +valuePairs.get(equation[0]).add(values[i]); |
| 56 | +valuePairs.get(equation[1]).add(1 /values[i]); |
44 | 57 | } |
45 | | -if (!pairs.containsKey(equation[1])) { |
46 | | -pairs.put(equation[1],newArrayList<>()); |
47 | | -valuePairs.put(equation[1],newArrayList<>()); |
48 | | - } |
49 | | -pairs.get(equation[0]).add(equation[1]); |
50 | | -pairs.get(equation[1]).add(equation[0]); |
51 | | -valuePairs.get(equation[0]).add(values[i]); |
52 | | -valuePairs.get(equation[1]).add(1 /values[i]); |
53 | | - } |
54 | 58 |
|
55 | | -double[]result =newdouble[queries.length]; |
56 | | -for (inti =0;i <queries.length;i++) { |
57 | | -String[]query =queries[i]; |
58 | | -result[i] =dfs(query[0],query[1],pairs,valuePairs,newHashSet<>(),1.0); |
59 | | -if (result[i] ==0.0) { |
60 | | -result[i] = -1.0; |
| 59 | +double[]result =newdouble[queries.length]; |
| 60 | +for (inti =0;i <queries.length;i++) { |
| 61 | +String[]query =queries[i]; |
| 62 | +result[i] =dfs(query[0],query[1],pairs,valuePairs,newHashSet<>(),1.0); |
| 63 | +if (result[i] ==0.0) { |
| 64 | +result[i] = -1.0; |
| 65 | + } |
61 | 66 | } |
| 67 | +returnresult; |
62 | 68 | } |
63 | | -returnresult; |
64 | | - } |
65 | 69 |
|
66 | | -privatedoubledfs(Stringstart,Stringend,Map<String,List<String>>pairs,Map<String,List<Double>>valuePairs,HashSet<String>set,doublevalue) { |
67 | | -if (set.contains(start)) { |
68 | | -return0.0; |
69 | | - } |
70 | | -if (!pairs.containsKey(start)) { |
71 | | -return0.0; |
72 | | - } |
73 | | -if (start.equals(end)) { |
74 | | -returnvalue; |
75 | | - } |
76 | | -set.add(start); |
| 70 | +privatedoubledfs(Stringstart,Stringend,Map<String,List<String>>pairs, |
| 71 | +Map<String,List<Double>>valuePairs,HashSet<String>set,doublevalue) { |
| 72 | +if (set.contains(start)) { |
| 73 | +return0.0; |
| 74 | + } |
| 75 | +if (!pairs.containsKey(start)) { |
| 76 | +return0.0; |
| 77 | + } |
| 78 | +if (start.equals(end)) { |
| 79 | +returnvalue; |
| 80 | + } |
| 81 | +set.add(start); |
77 | 82 |
|
78 | | -List<String>stringList =pairs.get(start); |
79 | | -List<Double>valueList =valuePairs.get(start); |
80 | | -doubletmp =0.0; |
81 | | -for (inti =0;i <stringList.size();i++) { |
82 | | -tmp =dfs(stringList.get(i),end,pairs,valuePairs,set,value *valueList.get(i)); |
83 | | -if (tmp !=0.0) { |
84 | | -break; |
| 83 | +List<String>stringList =pairs.get(start); |
| 84 | +List<Double>valueList =valuePairs.get(start); |
| 85 | +doubletmp =0.0; |
| 86 | +for (inti =0;i <stringList.size();i++) { |
| 87 | +tmp =dfs(stringList.get(i),end,pairs,valuePairs,set,value *valueList.get(i)); |
| 88 | +if (tmp !=0.0) { |
| 89 | +break; |
| 90 | + } |
85 | 91 | } |
| 92 | +set.remove(start); |
| 93 | +returntmp; |
86 | 94 | } |
87 | | -set.remove(start); |
88 | | -returntmp; |
89 | 95 | } |
90 | | - |
91 | 96 | } |