lincode 题目记录5 - python学习网

Course Schedule

选课方案问题，题目说的很清楚了就是bfs或者dfs，然后加个字典优化，弄了好久没弄出来··网上查的算法··提交的是bfs的算法，dfs的算法给的用例好像是递归太深了· python编译器直接崩了··本地调试也是直接崩了··

bfs的核心是用一个数组记录每个数字的深度··就是要上这个课之前你得上多少门课，把是0的都加到队列里边，后边遍历的时候遍历到这个点的时候减一，直到减完，遍历完了如果还有点的入度不为0 ，就不能完成

网站上的python不知道是啥版本·· 队列是大写的Q ，我本地的是python3.5 是小写的 ··dfs的递归好像通不过

class Solution:
    # @param {int} numCourses a total of n courses
    # @param {int[][]} prerequisites a list of prerequisite pairs
    # @return {boolean} true if can finish all courses or false
    def canFinish(self, numCourses, prerequisites):
        import Queue
        import sys
        sys.setrecursionlimit(1000000)
        if len(prerequisites)<2:return True
        dicp={}
        inlist=[0]*numCourses
        for p in prerequisites:
            dicp.setdefault(p[1],[])
            dicp[p[1]].append(p[0])
            inlist[p[0]] += 1
        q=Queue.Queue()
        for i in range(numCourses):
            if inlist[i] == 0:q.put(i)
        
        while not q.empty():
            cur=q.get()
            if cur not in dicp:continue
            for i in dicp[cur]:
                inlist[i] -=1
                if inlist[i]==0:q.put(i)
        
        for i in inlist:
            if i !=0 :return False

        return True  
        ''' DFS  
        visit=[0]*numCourses
        def canfinishdfs(visit,i):
            if visit[i]==-1:return False
            if visit[i]==1:return True
            visit[i]=-1
            if i in dicp:
                for cur in dicp[i]:
                    if not canfinishdfs(visit,cur):return False
            visit[i]=1
            return True
            
        for i in range(numCourses):
             if not canfinishdfs(visit,i):
                 return False
        
        return True
        '''

python学习网

分类

Course Schedule