Question 3 Evaluate Division

注意这道题是多个query查询的问题

• 每个来做，可能有重复运算，之后可以用flow，类dp的算法？

High Level

• it is a graph problem,

  • vertex: different character,

  • edge: equation for different character

  • undirected graph

• this is a reachable graph problem + calculate the weight

• dfs/ bfs to solve it

Middle Level

public double[] calEquation(List<List<String>> equations, double[] values, List<Liust<String>> queries) {
    // assume the input are valid
    
    double[] result = new double[queries.size()];
    
    // build Graph
    Map<String, Map<String, Double>> graph = buildGrpah(equations);
    
    int index = 0;
    for (List<String> query: queries) {
        Set<String> visited = new HashSet<>();
        String u = query.get(0);
        String v = query.get(1);
        if (u.equals(v)) { // 面试里不一定需要做检查，注意CART
            if (!graph.containsKey(u) || !graph.containsKey(v)) {
                result[index] = -1.0;
                index++;
            }else{
                result[index] = 1.0;
                index++;
            }
            continue;
        }
        result[index] = dfs(graph, visited, u, v, 1.0);
        result2[index] = bfs(graph, visited, u, v, 1.0);
        index++;
    }
    return result;
}
// return value的意义：目的是为了减脂6，
// 有结果，不应该是-1， 不然到不了（算不出来）结果应该是-1
// u 相当于current Node，
// v 相当于target Node
private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited, String u, String v, double result) {
    if (u.equals(v)) {
        return result;
    }
    visited.add(result);
    Map<String, Double> neis = graph.get(u);
    if (neis != null) {
        for (String key: neis.keySet()) {
            if (!visited.contains(key)) {
                double result = dfs(graph, visited, key, v, result * neis.get(key));
                if (result != -1.0) {
                    return result;
                }
            }
        }
    }
}


private double bfs(Map<String, Map<String, Double>> graph, Set<String> visited, String u, String v, double result) {
    Deque<Pair> queue = new ArrayDeque<>();
    Pair root = new Pari(u result);
    queue.offer(root);
    visited.add(root);
    while(!queue.isEmpty()) {
        Pari current = queue.poll();
        Map<String, Double> neis = graph.get(current.cur);
        if (neis != null) {
            for (String nei: neis.keySet()) {
                double newResult = current.result * neis.get(nei);
                if (nei.equals(v)){
                    return newResult;
                }
                Pair new Pair = new Pari(nei, newResult);
                if(visited.add(neiPair)) {
                    queue.offer(neiPair);
                }
            
            }
        }
    }
    return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, doubles[] values) {
    Map<String, Map<String, Double>> graph = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        double value = values[i];
        List<String> nodePair = equations.get(i);
        graph.putIfAbsent(nodePari.get(0), new HashMap<>());
        graph.putIfAbsent(nodePari.get(1), new HashMap<>());
        graph.get(nodePair.get(0)).put(nodePair.get(1), value);
        graph.get(nodePair.get(1)).put(nodePair.get(0), 1 / value);
    }
    return graph;
}




class Pair{
    String cur;
    double result;
    public Pair(String cur, double result) {
        this.cur = cur;
        this.result = result;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj == this) return true;
        if (!obj instanceof Pair) return false;
        Pair temp = (Pair) obj;
        return this.cur.equals(temp.cur) && this.result == temp.result;
    }
    @Override
    public int hashcode(Object obj) {
        return (int) this.result * 31 + this.cur.length() *31 *31;
    }
}

following up question:

• you may assume that evaluating the queries will not result in division by zero and

• what if there may exist contradictions, could you determine if there exist any contradictions? if yes return true otherwise return false

还是一个图问题，其实还是个reachable连通性的问题，不过什么叫做有contradictions，就是会不会存在另外一个方式到达一个点使得方式得到的result不同

• 我们的目的是寻求从start到target得reachable的方式

• 我们知道应有的结果，

  • 结果精度：Java/JavaScript，double判断，range：0.001 ==》 CART

  • 存不存在一个使得到达以后计算出的result和原始给定的，中途计算的

public boolean checkIfContainsContradictions(List<List<String>> equations, double[] values) {
    Set<String> allNodes = new HashSet<>();
    Map<String, Double> visited = new HashMap<>();
    Map<String, List<Pair>> graph = buildGraph(equations, values);
    
    // 不联通图里的联通分量遍历的要点，从所有没有出发过的点出发一次
    // DFS return value represent contradictions
    for (String node: nodes) {
        for (String node: nodes) {
            if (!visited.containsKey(node) & dfs(graph, visited, node, 1.0)) {
                return true;
            }
        }
        return false;
    }
    
}
private boolean dfs(Map<String List<Pair>> graph, Map<String, Double> visited, String curNode, double val) {
    if (visited.containsKey(curNode)) {
        return Math.abs(visited.get(curNode) - val) >= ERRRANGE;
    }
    visited.put(curNode, val);
    for (Pair nei: graph.getOrDefault(curNode, new ArrayList<>())) {
        if (dfs(graph, visited, nei.cur, val * nei.result)) {
            return true;
        }
    }
    return false;
}

private Map<String, List<Pair>> buildGraph(List<List<String>> equations, doubles[] values) {
    Map<String, Map<String, Double>> adjList = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        double value = values[i];
        List<String> nodePair = equations.get(i);
        graph.putIfAbsent(nodePari.get(0), new HashMap<>());
        graph.putIfAbsent(nodePari.get(1), new HashMap<>());
        graph.get(nodePair.get(0)).put(new Pair(nodePair.get(1), value);
        graph.get(nodePair.get(1)).put(new Pair(nodePair.get(0), 1 / value);
    }
    return adjList;
}




class Pair{
    String cur;
    double result;
    public Pair(String cur, double result) {
        this.cur = cur;
        this.result = result;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj == this) return true;
        if (!obj instanceof Pair) return false;
        Pair temp = (Pair) obj;
        return this.cur.equals(temp.cur) && this.result == temp.result;
    }
    @Override
    public int hashcode(Object obj) {
        return (int) this.result * 31 + this.cur.length() *31 *31;
    }
}