程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode-Course Schedule

leetcode-Course Schedule

編輯:C++入門知識

leetcode-Course Schedule


題目:leetcode

Course Schedule

 

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

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

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.


分析:

本題目可轉化為 “判斷有向圖中是否有環”。

1、把數組prerequisites中的內容放進哈希表table,table的key是課程編號,value是一個數組,記錄了key代表的課程的約束條件(即上完value中的課程,才能上key的課程)。如果每一門課程當成平面上的一個點,那麼key和value中的每一門課程,可以分別連成一條有向路徑。

2、利用回溯法,如果沒有環,則把相應的“路徑”刪除,直到把有向圖刪光。若有環,則整個程序返回false。

 

 

class Solution {
public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        if(prerequisites.size()<=1)
            return true;
        
        unordered_map> table;
        for(auto &i:prerequisites)
        {
            table[i[0]].push_back(i[1]);
        }
       vector path;
        while(!table.empty())
        {
            auto it=table.begin();
            path.push_back(it->first);
            if(HasLoop(table,it->first,path))
                return false;
            path.pop_back();
        }
        return true;
    }
    //判斷是否有環,有環的話返回真,否則返回假
    bool HasLoop( unordered_map> &table,const int &begin,vector &path)
    {
       if(table.count(begin)==0)
         return false;
       while(!table[begin].empty())
       {
           int temp=table[begin].back();
           if(find(path.begin(),path.end(),temp)!=path.end())
                return true;
            path.push_back(temp);
           if(HasLoop(table,temp,path))
                return true;
            path.pop_back();
            table[begin].pop_back();
       }
       table.erase(begin);
       return false;
    }
    
};


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved