leetcode笔记（三）207. 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?

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 = ; i < numCourses; i++)

        {

            outNodes[i] = ;

        }

        int n = prerequisites.size();

        for(int i = ; i < n; i++)

        {

            outNodes[prerequisites[i].first] += ;

            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 = ; i < numCourses; i++)

            {

                // remove the outNodes and update outNodes vector

                if(outNodes[i] == )

                {

                    outNodes[i] -= ;

                    for(int j = ; j < inEdges[i].size(); j++)

                    {

                        outNodes[inEdges[i][j]] -= ;

                    }

                    toFind = true;

                    leftNode -= ;

                    break;

                }

            }

        }

        return (leftNode == );

    }

};

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

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

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

p.first = p.second;

巴特西

leetcode笔记（三）207. Course Schedule

最新文章

热门文章