【題目】

　　 ?你有n門課程需要上，幾位0到n-1.

　　 ?有些課程需要一些預備課程，例如：上課程0前需要先上課程1，表示為對[0,1]

? ? ? ? 假設給你所有課程和這些課程的對關系，有可能上完所有課程嗎？

? ? ? ? 舉例：

? ? ? ? 2 , [[1,0]]

? ? ? ? 這有2個課程需要完成，完成課程1前需要完成課程0，所以是可能的。

? ? ? ? 2 , [[1,0],[0,1]]

? ? ? ? 這有2個課程需要完成，完成課程1前需要完成課程0，完成課程0前需要完成課程1，所以是不可能的。

【分析】

　　 ?1. 問題可以抽象為圖的問題，就是判斷圖里是否存在環

? ? ? ? 2. 解決方法：（拓撲排序），求出所有點的入度，循環遍歷n（n為點個數）次，每一次循環里判斷是否有點的入度　　為0；若所有的點的入度都不為0，return false;

　　　　　　　　 ? ??反之，當前點的入度置為-1，進入下一次循環；跳出循環后，return true

【算法實現】

public class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<Set<Integer>> ls = new ArrayList<Set<Integer>>();for(int i=0; i<numCourses; i++) {ls.add(new HashSet<Integer>());}for(int i=0; i<prerequisites.length; i++) {ls.get(prerequisites[i][1]).add(prerequisites[i][0]);}int[] preNum = new int[numCourses];for(int i=0; i<numCourses; i++) {Set<Integer> set = ls.get(i); Iterator<Integer> it = set.iterator();while(it.hasNext()) {preNum[it.next()]++;}}for(int i=0; i<numCourses; i++) {int j;for(j=0; j<numCourses; j++) {if(preNum[j]==0)break;}if(j==numCourses)return false;preNum[j] = -1;Set<Integer> set = ls.get(j);Iterator<Integer> it = set.iterator();while(it.hasNext()) {preNum[it.next()]--;}}return true;} }

?

轉載于:https://www.cnblogs.com/hwu2014/p/4518015.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的207-Course Schedule的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。