Java Memorize BFS without Recursion 中文版


  • 0
    B

    貌似没有我这种答案的。但是私以为我这个答案是最快的。弗洛伊德算法是O(n^3),一些高票答案的话用DFS但是没有做剪枝,貌似是O(n^2),错了还请纠正。感觉这题对于一个query,其实也就是要找图中两点之间的一条路,那么应该是BFS比较好吧。我这个应该是O(n)的,错了请纠正。希望对大家有帮助。

    Floyd Alg is O(n^3). DFS without memorize can be O(n^2). I guess BFS with memorize is O(n). Correct me if I am wrong.

        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            
            Map<String, Map<String, Double>> dp = new HashMap<>();
            Map<String, Set<String>> graph = new HashMap<>();
            init(dp, graph, equations, values);
            
            double[] result = new double[queries.length];
            for (int k = 0; k < result.length; k++) {
                String start = queries[k][0];
                String end = queries[k][1];
                if (!dp.containsKey(start) || !dp.containsKey(end)) {
                    result[k] = -1;
                    continue;
                }
                result[k] = bfs(start, end, dp, graph, new HashSet<>());
            }
            return result;
        }
        
        public double bfs(String start, String end, Map<String, Map<String, Double>> dp, Map<String, Set<String>> graph, Set<String> visited) {
            if (dp.get(start).containsKey(end)) return dp.get(start).get(end);
            Queue<String> q = new LinkedList<>();
            q.offer(start);
            visited.add(start);
            while (q.size() > 0) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    String node = q.poll();
                    if (dp.get(node).containsKey(end)) {
                        dp.get(start).put(end, dp.get(start).get(node) * dp.get(node).get(end));
                        dp.get(end).put(start, 1 / dp.get(start).get(end));
                        return dp.get(start).get(end); 
                    }
                    for (String child : graph.get(node)) {
                        if (!visited.contains(child)) {
                            visited.add(child);
                            q.offer(child);
                            dp.get(start).put(child, dp.get(start).get(node)*dp.get(node).get(child));
                            dp.get(child).put(start, 1 / dp.get(start).get(child));
                        }
                    }
                }
            }
            return -1;
        }
        
        public void init(Map<String, Map<String, Double>> dp, Map<String, Set<String>> graph, String[][] equations, double[] values) {
            for (int k = 0; k < values.length; k++) {
                String start = equations[k][0], end = equations[k][1];
                //for dp init
                if (!dp.containsKey(start)) dp.put(start, new HashMap<>());
                if (!dp.containsKey(end)) dp.put(end, new HashMap<>());
                dp.get(start).put(start, 1.0);
                dp.get(end).put(end, 1.0);
                dp.get(start).put(end, values[k]);
                dp.get(end).put(start, 1.0 / values[k]);
                //for adjacency graph init
                if (!graph.containsKey(start)) graph.put(start, new HashSet<>());
                if (!graph.containsKey(end)) graph.put(end, new HashSet<>());
                graph.get(start).add(end);
                graph.get(end).add(start);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.