leetcode笔记(三)207. Course Schedule

2018-06-27 09:42:50来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

  • 题目描述(原题目链接)

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?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: 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.

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.
  • 解题思路

这道题目是检测图内是否有环的应用题目,解决方案是经典的拓扑排序即可。之前实习面试的时候,太紧张没能想到拓扑排序。

所以,这次也特意选择拓扑排序类的题目做一下。感觉确实是不熟悉,简单的程序也调了挺久。

解这道题的基本思路如下:

    •  针对每个节点,记录依赖它的节点,以及自身依赖节点的数目。
    • 选出依赖节点数目为0的节点,移除,更新依赖它的节点的依赖节点数目。
    • 循环上述步骤,直至无点可移。
    • 判断剩余点数。 

结合这个思路,编码实现如下:

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //initiate outNodes and inEdges
        vector<int> outNodes(numCourses);
        vector<vector<int>> inEdges(numCourses);
        for(int i = 0; i < numCourses; i++)
        {
            outNodes[i] = 0;
        }
        int n = prerequisites.size();
        for(int i = 0; i < n; i++)
        {
            outNodes[prerequisites[i].first] += 1;
            inEdges[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        
        int leftNode = numCourses;
        bool toFind = true;
        while(toFind)
        {
            // find next node to move
            toFind = false;
            for(int i = 0; i < numCourses; i++)
            {
                // remove the outNodes and update outNodes vector
                if(outNodes[i] == 0)
                {
                    outNodes[i] -= 1;
                    for(int j = 0; j < inEdges[i].size(); j++)
                    {
                        outNodes[inEdges[i][j]] -= 1;
                    }
                    
                    toFind = true;
                    leftNode -= 1;
                    break;
                }
            }
        }
        
        return (leftNode == 0);
    }
};

 

附加知识:pair的基本使用。

pair<int, int> p(1,2);

pair<int, int> p; p = make_pair(1,2);

p.first = p.second;  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:《Effective C++》读书笔记 条款03 尽可能使用const 使代码更加

下一篇:BZOJ1086: [SCOI2005]王室联邦(贪心,分块?)