Course Schedule II

思路:
典型的拓扑排序。

实现:
一看到这种给n个点,点是从0到n-1,就要考虑一维数组节省空间。那么可以定义
List[] edges =  new ArrayList[numCourses];
int[] degrees = new int[numCourses];
找degree和edge的方法很简单。

每一次从edges里面取出点一定先要把入度递减1。是因为这一条edge已经遍历过了。

在BFS的时候需要一个incremented index来不断给结果数组赋值。代码如下:

 public class Solution {  
   /*  
    * @param numCourses: a total of n courses  
    * @param prerequisites: a list of prerequisite pairs  
    * @return: the course order  
    */  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
     // write your code here  
     List[] edges = new ArrayList[numCourses];  
     int[] degrees = new int[numCourses];   
     for (int i = 0;i < numCourses; i++)  
       edges[i] = new ArrayList<Integer>();  
     for(int i = 0; i < prerequisites.length; i++)  
     {  
       degrees[prerequisites[i][0]]++;  
       edges[prerequisites[i][1]].add(prerequisites[i][0]);  
     }  
     // get starting nodes.  
     Queue<Integer> queue = new LinkedList<>();  
     int[] result = new int[numCourses];  
     int count = 0;  
     for(int i = 0; i < numCourses; i++)  
     {  
       if(degrees[i] == 0)  
       {  
         queue.add(i);  
         result[count++] = i;  
       }  
     }  
     while(!queue.isEmpty())  
     {  
       int curNode = queue.poll();  
       for(int i = 0; i < edges[curNode].size(); i++)  
       {  
         int n = (int)edges[curNode].get(i);  
          degrees[n]--;  
         if(degrees[n] == 0)  
         {  
           result[count++] = n;  
           queue.add(n);  
         }  
       }  
     }  
     if(count == numCourses)  
       return result;  
     return new int[0];  
   }  
 }  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array