Help please! Why my codes cannot pass the test with 2000 nodes? so wierd


  • 0
    J
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            Map<Integer, Integer> indegree = new HashMap<>();
            for(int i=0; i<numCourses; i++){
                indegree.put(i, 0);
                graph.put(i, new HashSet<Integer>());
            }
            Set<String> edges = new HashSet<>();
            for(int i=0; i<prerequisites.length; i++){
                int prev = prerequisites[i][1];
                int next = prerequisites[i][0];
                if(!edges.contains(Integer.toString(prev)+Integer.toString(next))){
                   graph.get(prev).add(next);
                   indegree.put(next, indegree.get(next)+1);
                   edges.add(Integer.toString(prev)+Integer.toString(next));
                }
            }
            Queue<Integer> schedule = new LinkedList<>();
            Queue<Integer> queue = new LinkedList<>();
            for(int i=0; i<numCourses; i++){
                if(indegree.get(i) == 0){
                    queue.offer(i);
                }
            }
            while(!queue.isEmpty()){
                int course = queue.poll();
                schedule.offer(course);
                Set<Integer> set = graph.get(course);
                for(Integer next : set){
                    if(indegree.get(next) == 1){
                        queue.offer(next);
                    }
                    indegree.put(next, indegree.get(next)-1);
                }
            }
            if(schedule.size() != numCourses) return new int[0];
            int[] ans = new int[schedule.size()];
            int counter = 0;
            while(!schedule.isEmpty()){
                ans[counter] = schedule.poll();
                counter++;
            }
            return ans; 
        }
    

  • 0
    J

    solved problem, here has bugs:

    edges.contains(Integer.toString(prev)+Integer.toString(next))

    should be edges.contains(Integer.toString(prev)+"->"+Integer.toString(next))


Log in to reply
 

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