1、首先将边转化成邻接表的形式,总的来说没有

作者: 编程  发布:2019-08-30

[LeetCode] Course Schedule II

Course Schedule II

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

解题思路:

1、首先将边转化成邻接表的款型,然后渐渐找那两个从没前人课程的课,若找到一门课从不四驱课,出席结果中,然后在图中去除那条边。

 

class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector result;
        if(numCourses<=0){
            return result;
        }
        //将图转化成邻接表的形式。
        vector> graph(numCourses, set());
        for(int i=prerequisites.size() - 1; i>=0; i--){
            graph[prerequisites[i].first].insert(prerequisites[i].second);
        }
        bool flag[numCourses];  //标记是否已经加到了result里面了
        memset(flag, 0, sizeof(bool) * numCourses);
        while(result.size()时间复杂度为O(n^2),比较慢,虽然AC了,但是花了1492ms。 2、可以采用空间换时间的办法,记录一个反向图,若找到一门课程后,直接删除对应的边,而无需遍历整张图。另外,记录当前还剩下的那些节点。空间加倍,时间为591ms。 class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector result;
        if(numCourses<=0){
            return result;
        }
        //将图转化成邻接表的形式。
        vector> graph(numCourses, set());
        vector> reverseGraph(numCourses, vector());    //反向图
        for(int i=prerequisites.size() - 1; i>=0; i--){
            graph[prerequisites[i].first].insert(prerequisites[i].second);
            reverseGraph[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        set leftNode;  //还剩下哪些节点
        for(int i=0; i::iterator it=leftNode.begin(); it!=leftNode.end(); it  ){
                if(graph[*it].empty()){
                    index = *it;
                    break;
                }
            }
            if(index<0){
                break;
            }
            result.push_back(index);
            leftNode.erase(index);
            //清除所有以该课程为前驱的边
            for(int i=0; i 

] Course Schedule II Course Schedule II 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 Schedule的解法基本是一律的。小编照旧利用了BFS举办拓扑排序,总的来讲未有什么样新的坑点。

Course Schedule II

Total Accepted: 13015 Total Submissions: 64067 Difficulty: Medium

 

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

图片 1图片 2

 1 struct edge{
 2     int to;
 3     edge(){ this->to = 0;}
 4     edge(int t){ this->to = t;}
 5 };
 6 class Solution {
 7 public:
 8     void addEdge(vector<edge> &edgelist, vector<vector<int>> &G, int from, int to){
 9         edge e = edge(to);
10         edgelist.push_back(e);
11         G[from].push_back(edgelist.size()-1);
12     }
13     /*  calculate the indegree of all nodes in graph  */
14     void calInDegree(vector<int> &inDegree, vector<edge> edgelist, vector<vector<int>> G){
15         for(int i=0;i<G.size();i  ){
16             for(int k=0;k<G[i].size();  k){
17                 edge e = edgelist[G[i][k]];
18                   inDegree[e.to];
19             }
20         }
21     }
22     void topologicalSort(vector<int> &ret, vector<int> inDegree, vector<edge> edgelist, vector<vector<int>> G){
23         stack<int> st; 
24         while(!st.empty()) st.pop();
25         for(int i=0;i<G.size();  i){
26             if(!inDegree[i])  st.push(i);
27         }
28         while(!st.empty()){
29             int k = st.top(); st.pop();
30             ret.push_back(k);
31             for(int i=0;i<G[k].size();  i){
32                 edge e = edgelist[G[k][i]];
33                 --inDegree[e.to];
34                 if(!inDegree[e.to]) st.push(e.to);
35             }
36         }
37         vector<int> ans;
38         vector<int>::reverse_iterator pt=ret.rbegin();
39         for(;pt!=ret.rend();  pt) ans.push_back(*pt);
40         ret = ans;
41     }
42     vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
43         vector<edge> edgelist; edgelist.clear();
44         vector<vector<int> > G(numCourses);
45         for(int i=0;i<G.size();  i) G[i].clear();
46         vector<int> inDegree(numCourses); 
47         for(int i=0;i<G.size();  i) inDegree[i]=0;
48         
49         for(int i=0;i<prerequisites.size();  i){
50             pair<int, int> pr = prerequisites[i];
51             addEdge(edgelist, G, pr.first, pr.second);
52         }
53         
54         calInDegree(inDegree, edgelist, G);
55         
56         vector<int> ret; ret.clear();
57         topologicalSort(ret,inDegree,edgelist,G);
58         
59         if(ret.size() < numCourses){ret.clear(); return ret;}
60         else return ret;
61     }
62 };

View Code

 

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]
. Another correct ordering is[0,2,1,3].

Course Schedule II题解

原创小说,拒绝转发

标题来源:


2, [[1,0]]

Description

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> map(numCourses);
        vector<int> in(numCourses, 0);
        auto n = prerequisites.size();
        for (auto i=0; i<n; i  ) {
            map[prerequisites[i].second].push_back(prerequisites[i].first);
            in[prerequisites[i].first]  ;
        }
        vector<int> res;
        while (res.size() < numCourses) {
            auto i = 0;
            for (i=0; i<numCourses; i  )
                if (in[i] == 0)
                    break;
            if (i == numCourses)
                return vector<int>();
            res.push_back(i);
            in[i] = -1;
            for (auto j=0; j<map[i].size(); j  )
                in[map[i][j]]--;
        }
        return res;
    }
};

Solution

class Solution {
private:
    vector<int> inDegree;
    vector<bool> isFinish;
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        inDegree.resize(numCourses);
        isFinish.resize(numCourses);
        int i, v;
        for (i = 0; i < numCourses; i  ) {
            inDegree[i] = 0;
            isFinish[i] = false;
        }
        for (i = 0; i < prerequisites.size(); i  ) 
            inDegree[prerequisites[i].first]  ;

        queue<int> vq;
        for (i = 0; i < numCourses; i  ) {
            if (inDegree[i] == 0)
                vq.push(i);
        }

        vector<int> resultVec;
        if (vq.empty())
            return resultVec;

        while (!vq.empty()) {
            v = vq.front();
            vq.pop();
            resultVec.push_back(v);
            isFinish[v] = true;
            for (i = 0; i < prerequisites.size(); i  ) {
                if (v == prerequisites[i].second) {
                    inDegree[prerequisites[i].first]--;
                    if (inDegree[prerequisites[i].first] == 0 && !isFinish[prerequisites[i].first])
                        vq.push(prerequisites[i].first);
                }
            }
        }

        if (resultVec.size() == numCourses) {
            return resultVec;
        }
        else {
            vector<int> r;
            return r;
        }
    }
};

难题来源
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]

Note:

4, [[1,0],[2,0],[3,1],[3,2]]
  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

和在此之前做过的Course Schedule类似,其实就是拓扑排序。代码如下:

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:

本文由9159.com发布于编程,转载请注明出处:1、首先将边转化成邻接表的形式,总的来说没有

关键词: 9159.com