【leetcode】207. Course Schedule

深藏阁楼爱情的钟 2022-01-07 11:29 298阅读 0赞

题目如下：

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:

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

Example 2:

  1. Input: 2, [[1,0],[0,1]]
  2. Output: false
  3. Explanation: There are a total of 2 courses to take. 
  4.              To take course 1 you should have finished course 0, and to take course 0 you should
  5.              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.

解题思路：如果某一种输入课程无法被安排，那么一定存在至少这样一门课：通过BFS/DFS的方法从这门课开始，依次遍历需要安排在这门课后面的其他课，最终还会回到这门课，即组成了一个环。我们只有遍历所有的课，看看有没有哪门课会形成环路即可。

代码如下：

  1. class Solution(object):
  2.     def canFinish(self, numCourses, prerequisites):
  3.         """
  4.         :type numCourses: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: bool
  7.         """
  8.         dic = {}
  9.         for cou,pre in prerequisites:
  10.             if pre not in dic:
  11.                 dic[pre] = [cou]
  12.             else:
  13.                 dic[pre].append(cou)
  15.         for i in range(numCourses):
  16.             visit = [0] * numCourses
  17.             queue = [i]
  18.             start = None
  19.             while len(queue) > 0:
  20.                 inx = queue.pop(0)
  21.                 if start == None:
  22.                     start = inx
  23.                 elif inx == start:
  24.                     return False
  25.                 if visit[inx] == 1:
  26.                     continue
  27.                 visit[inx] = 1
  28.                 if inx in dic and len(dic[inx]) > 0:
  29.                     queue += dic[inx]
  30.         return True

转载于:https://www.cnblogs.com/seyjs/p/10456295.html

发表评论

表情：
评论列表 （有 0 条评论，298人围观）

还没有评论，来说两句吧...

相关阅读