LeetCode 207.课程表 Python题解

课程表

# coding=utf-8
# Creator:Mr.Zhao
# Creation time:2024/3/11 21:06

# 课程表
"""
你这个学期必须选修numCourses门课程，记为0到numCourses - 1 。
在选修某些课程之前需要一些先修课程。
先修课程按数组prerequisites给出，其中prerequisites[i]=[ai, bi]，
表示如果要学习课程ai则必须先学习课程bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false
"""

class Solution1: # 常规思路过不了 需要进阶了 
    def canFinish(self, numCourses: int, prerequisites) -> bool:
        course = [[] for i in range(numCourses)]
        for co in prerequisites:
            course[co[1]].append(co[0]) 
            # 这个代表 先完成1才能学0 最后呈现效果就是 
            # 想完成course[i]里面的课程数字必须要先完成第i门课
            # 所以也就是说 对course[i]里面的数字(a,b,c,d...)来说
            # course[a].....course[.]里面不能有i即可完成  
        print(course)
        for i,content in enumerate(course):
            for con in content:
                if i in course[con]:
                    return False
        return True

class Solution:
    def canFinish(self, numCourses, prerequisites):
        # 就是每个课程学的时候有多少个前置要学的课程
        # 考虑更加全面
        iner = [0] * numCourses  
        course = [[] for i in range(numCourses)]
        for co in prerequisites:
            course[co[1]].append(co[0]) 
            iner[co[0]]+=1
        
        # 一定存在没有前置课程要学的节点如果不存在那就false了
        root, result = [i for i in range(numCourses) if iner[i] == 0], []
        print(iner)
        print(course)
        print(root)
        def dfs(node):
            result.append(node)
            for i in course[node]: 
                # 这个节点里面对应的课程
                # 前置课程就都会少一个
                iner[i] -= 1
                if iner[i] == 0:
                    dfs(i)
        for x in root:
            dfs(x)
        # 返回最后结果 可以过https://leetcode.cn/problems/QA2IGt/ 这个题
        return True if len(result) == numCourses else False 

pre = [[1,4],[2,4],[3,1],[3,2]]
numCourses = 5
a = Solution()
print(a.canFinish(numCourses,pre))