What is the best way to solve Course Schedule II?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

코스일정II

'Course Schedule II' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

수강해야 하는 총 numCourses 과정이 있으며 0부터 numCourses - 1까지 레이블이 지정됩니다. 전제 조건[i] = [ai, bi]는 ai 과정을 수강하려면 먼저 bi 과정을 수강해야 함을 나타내는 배열 전제 조건이 제공됩니다.

모든 강좌를 마치기 위해 수강해야 하는 강좌의 순서를 반환합니다. 유효한 답변이 많으면 그 중 하나를 반환하십시오. 모든 과정을 완료할 수 없는 경우 빈 배열을 반환합니다.

findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int] 함수를 작성하세요.

제약

•1 <= numCourses <= 2000
•0 <= len(prerequisites) <= 5000
•prerequisites[i].length == 2
•0 <= ai, bi < numCourses

예

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Output

[0,1]

Explanation

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2

Input

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output

[0,2,1,3]

Explanation

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def find_order_opt(numCourses, prerequisites):
    adj = {i: [] for i in range(numCourses)}
    for crs, pre in prerequisites: adj[crs].append(pre)
    output = []
    visit, cycle = set(), set()
    def dfs(crs):
        if crs in cycle: return False
        if crs in visit: return True
        cycle.add(crs)
        for pre in adj[crs]:
            if not dfs(pre): return False
        cycle.remove(crs)
        visit.add(crs)
        output.append(crs)
        return True
    for c in range(numCourses):
        if not dfs(c) == False: return []
    return output

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def find_order_brute(numCourses, prerequisites):
    adj = {i: [] for i in range(numCourses)}
    for crs, pre in prerequisites: adj[crs].append(pre)
    res = []
    def dfs(crs, visiting, visited):
        if crs in visiting: return False
        if crs in visited: return True
        visiting.add(crs)
        for pre in adj[crs]:
            if not dfs(pre, visiting, visited): return False
        visiting.remove(crs)
        visited.add(crs)
        res.append(crs)
        return True
    visit, vstd = set(), set()
    for c in range(numCourses):
        if not dfs(c, visit, vstd): return []
    return res