615.課程表

描述

現(xiàn)在你總共有 n 門課需要選践叠,記為 0 到 n - 1.
一些課程在修之前需要先修另外的一些課程锌订,比如要學習課程 0 你需要先學習課程 1 ,表示為[0,1]
給定n門課以及他們的先決條件,判斷是否可能完成所有課程?

樣例

給定 n = 2怒竿,先決條件為 [[1,0]] 返回 true
給定 n = 2,先決條件為 [[1,0],[0,1]] 返回 false

代碼

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // edges用來存儲每一門課程對應的所有后續(xù)課程
        // 此處新建edges的寫法要注意
        List[] edges = new ArrayList[numCourses];
        int[] degree = new int[numCourses];
        
        // edges[i]本身就是一個動態(tài)數(shù)組扩氢,初始化edges
        for (int i = 0;i < numCourses; i++)
            edges[i] = new ArrayList<Integer>();
            
        for (int i = 0; i < prerequisites.length; i++) {
            // 題目給出的prerequisites[i][1]是先修課程耕驰,prerequisites[i][0]是后續(xù)課程
            // 統(tǒng)計學習某門課需要先修的課程數(shù)目,即入度
            degree[prerequisites[i][0]]++ ;
            // 即把某門課的后續(xù)課程全部加入到該課對應的edges數(shù)組中
            edges[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        
        // degree數(shù)組中i代表的的是某一門課程
        // 把度為0的課程加入隊列
        Queue queue = new LinkedList();
        for(int i = 0; i < degree.length; i++){
            if (degree[i] == 0) {
                queue.add(i);
            }
        }
        
        int count = 0;
        while(!queue.isEmpty()){
            // 隊列里存儲的是Integer
            int course = (int)queue.poll();
            count ++;
            // n代表當前課程的后續(xù)課程的數(shù)目
            int n = edges[course].size();
            // 每處理一門課程,該課程的后續(xù)課程的度都要-1
            for(int i = 0; i < n; i++){
                int pointer = (int)edges[course].get(i);
                degree[pointer]--;
                if (degree[pointer] == 0) {
                    queue.add(pointer);
                }
            }
        }
        
        // 處理的課程數(shù)目等于所有課程說明所有課程之間可以構成拓撲排序
        return count == numCourses;
    }
}
最后編輯于
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末录豺,一起剝皮案震驚了整個濱河市朦肘,隨后出現(xiàn)的幾起案子截酷,更是在濱河造成了極大的恐慌铐懊,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,496評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件洒敏,死亡現(xiàn)場離奇詭異咏花,居然都是意外死亡趴生,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,407評論 3 392
  • 文/潘曉璐 我一進店門昏翰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來苍匆,“玉大人,你說我怎么就攤上這事棚菊〗龋” “怎么了?”我有些...
    開封第一講書人閱讀 162,632評論 0 353
  • 文/不壞的土叔 我叫張陵统求,是天一觀的道長检碗。 經(jīng)常有香客問我,道長码邻,這世上最難降的妖魔是什么折剃? 我笑而不...
    開封第一講書人閱讀 58,180評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮冒滩,結果婚禮上微驶,老公的妹妹穿的比我還像新娘浪谴。我一直安慰自己开睡,他們只是感情好,可當我...
    茶點故事閱讀 67,198評論 6 388
  • 文/花漫 我一把揭開白布苟耻。 她就那樣靜靜地躺著篇恒,像睡著了一般。 火紅的嫁衣襯著肌膚如雪凶杖。 梳的紋絲不亂的頭發(fā)上胁艰,一...
    開封第一講書人閱讀 51,165評論 1 299
  • 那天,我揣著相機與錄音,去河邊找鬼腾么。 笑死奈梳,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的解虱。 我是一名探鬼主播攘须,決...
    沈念sama閱讀 40,052評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼殴泰!你這毒婦竟也來了于宙?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 38,910評論 0 274
  • 序言:老撾萬榮一對情侶失蹤悍汛,失蹤者是張志新(化名)和其女友劉穎捞魁,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體离咐,經(jīng)...
    沈念sama閱讀 45,324評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡谱俭,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,542評論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了宵蛀。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片旺上。...
    茶點故事閱讀 39,711評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖糖埋,靈堂內(nèi)的尸體忽然破棺而出宣吱,到底是詐尸還是另有隱情,我是刑警寧澤瞳别,帶...
    沈念sama閱讀 35,424評論 5 343
  • 正文 年R本政府宣布征候,位于F島的核電站,受9級特大地震影響祟敛,放射性物質發(fā)生泄漏疤坝。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,017評論 3 326
  • 文/蒙蒙 一馆铁、第九天 我趴在偏房一處隱蔽的房頂上張望跑揉。 院中可真熱鬧,春花似錦埠巨、人聲如沸历谍。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,668評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽望侈。三九已至,卻和暖如春勋桶,著一層夾襖步出監(jiān)牢的瞬間脱衙,已是汗流浹背侥猬。 一陣腳步聲響...
    開封第一講書人閱讀 32,823評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留捐韩,地道東北人退唠。 一個月前我還...
    沈念sama閱讀 47,722評論 2 368
  • 正文 我出身青樓,卻偏偏與公主長得像荤胁,于是被迫代替她去往敵國和親铜邮。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,611評論 2 353

推薦閱讀更多精彩內(nèi)容

  • Spring Cloud為開發(fā)人員提供了快速構建分布式系統(tǒng)中一些常見模式的工具(例如配置管理寨蹋,服務發(fā)現(xiàn)松蒜,斷路器,智...
    卡卡羅2017閱讀 134,651評論 18 139
  • 樹形動態(tài)規(guī)劃已旧,顧名思義就是樹+DP秸苗,先分別回顧一下基本內(nèi)容吧:動態(tài)規(guī)劃:問題可以分解成若干相互聯(lián)系的階段,在每一個...
    Mr_chong閱讀 1,484評論 0 2
  • 背景 一年多以前我在知乎上答了有關LeetCode的問題, 分享了一些自己做題目的經(jīng)驗运褪。 張土汪:刷leetcod...
    土汪閱讀 12,743評論 0 33
  • 曾在田野山地里翻滾惊楼,也曾留戀于港臺故事集連續(xù)劇,或許躲在被窩里偷偷看青澀的江湖秸讹,抑或是匍匐于勤學苦讀的書山無涯之前...
    七里汀閱讀 256評論 0 1
  • 聽說檀咙,他去了遠方 聽說,她將成為別人的新娘 聽說璃诀,他已衣錦還鄉(xiāng) 聽說弧可,她現(xiàn)在幸福美滿 聽說,他們已白發(fā)蒼蒼 聽說劣欢,...
    鄉(xiāng)凝閱讀 264評論 0 0