Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
- Map<String, Map<String, Double>> map = new HashMap<>();
- for(int i = 0; i < equations.length; i++)
- {
- String[] eq = equations[i];
- double v = values[i];
- String from = eq[0], to = eq[1];
- if(!map.containsKey(from)) map.put(from, new HashMap<>());
- if(!map.containsKey(to)) map.put(to, new HashMap<>());
- map.get(from).put(to, v);
- // map.get(from).put(from, 1.0);
- map.get(to).put(from, 1.0 / v);
- // map.get(to).put(to, 1.0);
- }
- double[] re = new double[queries.length];
- for(int i = 0; i < queries.length; i++)
- {
- String[] q = queries[i];
- String from = q[0], to = q[1];
- re[i] = calc(from, to, map);
- }
- return re;
- }
- double calc(String from, String to, Map<String, Map<String, Double>> map)
- {
- if(!map.containsKey(from)) return -1.0;
- if(map.get(from).containsKey(to)) return map.get(from).get(to);
- if(map.containsKey(to) && map.get(to).containsKey(from)) return 1.0 / map.get(to).get(from);
- Queue<String> q = new LinkedList<>();
- Map<String, Double> map2 = map.get(from);
- for(String next : map2.keySet())
- q.offer(next);
- // Set<String> visited = new HashSet<>();
- while(!q.isEmpty())
- {
- String poll = q.poll();
- double val = map2.get(poll);
- if(poll.equals(to)) return val;
- if(!map.containsKey(poll)) continue;
- for(String next : map.get(poll).keySet())
- {
- if(map2.containsKey(next)) continue;
- map2.put(next, val * map.get(poll).get(next));
- q.offer(next);
- }
- }
- return -1.0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement