<Graph> 133 399

扫码查看

133. Clone Graph

我们也可以使用 BFS 来遍历图,使用队列 queue 进行辅助,还是需要一个 HashMap 来建立原图结点和克隆结点之间的映射。先克隆当前结点,然后建立映射,并加入 queue 中,进行 while 循环。在循环中,取出队首结点,遍历其所有 neighbor 结点,若不在 HashMap 中,我们根据 neigbor 结点值克隆一个新 neighbor 结点,建立映射,并且排入 queue 中。然后将 neighbor 结点在 HashMap 中的映射结点加入到克隆结点的 neighbors 数组中即可

Map.containsKey() :是否含有key

Map.get(key) :  获取key对应的value

class Solution {
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node newNode = new Node(node.val, new ArrayList<>());
        map.put(node, newNode);

        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            for(Node nei : cur.neighbors){
                if(!map.containsKey(nei)){
                    map.put(nei, new Node(nei.val, new ArrayList<>()));
                    queue.add(nei);
                }
                map.get(cur).neighbors.add(map.get(nei));
            }
        }
        return newNode;
    }
}

399. Evaluate Division

用有向图的方法做,先存入图中,再用DFS遍历。

Map.keySet() : 获取map对应的所有的key值。

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> g = new HashMap<>();
        buildGraph(g, equations, values);

        double[] res = new double[queries.size()];
        Arrays.fill(res, -1.0);
        int index = 0;
        for(List<String> q : queries){
            String a = q.get(0);
            String b = q.get(1);

            if(!g.containsKey(a) || !g.containsKey(b)){
                index++;
                continue;
            }else{
                dfs(g, a, b, res, index, new HashSet<>(), 1.0);
                index++;
            }
        }
        return res;
    }

    private void dfs(Map<String, Map<String, Double>> g, String a, String b, double[] res,
                     int index, Set<String> visited, double tmp){
        visited.add(a);

        if(g.get(a) == null || g.get(a).size() == 0){
            return;
        }
        if(g.get(a).containsKey(b)){
            res[index] = g.get(a).get(b) * tmp;
            return;
        }

        for(String next : g.get(a).keySet()){
            if(visited.contains(next)) continue;
            dfs(g, next, b, res, index, visited, g.get(a).get(next)*tmp);
        }
    }

    private void buildGraph(Map<String, Map<String, Double>> g, List<List<String>> equations, double[] values){
        int index = 0;
        for(List<String> e : equations){
            String a = e.get(0);
            String b = e.get(1);
            g.putIfAbsent(a, new HashMap<>());
            g.putIfAbsent(b, new HashMap<>());
            g.get(a).put(b, values[index]);
            g.get(b).put(a, 1.0 / values[index]);
            index++;
            g.get(a).put(a, 1.0);
            g.get(b).put(b, 1.0);
        }
    }
}
12-15 07:02
查看更多