Course Schedule
Jest numCourses kursów, ponumerowanych od 0 do numCourses-1. Każda para [a, b] w prerequisites oznacza, że musisz ukończyć kurs b, zanim rozpoczniesz kurs a. Zwróć true, jeśli istnieje kolejność, która pozwala ukończyć wszystkie kursy, a false, jeśli takiej kolejności nie ma.
Funkcja
- numCoursesinteger
- liczba kursów
- prerequisitesinteger-2d-array
- pary [a, b], z których każda oznacza, że kurs b odbywa się przed kursem a
- Zwracaboolean
- true, jeśli każdy kurs można ukończyć, w przeciwnym razie false
Ograniczenia
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Każda para
[a, b]spełnia warunek0 ≤ a, b < numCourses. - Żadna para nie pojawia się dwukrotnie.
- A para może dwukrotnie wskazywać ten sam kurs:
[a, a]. Ten kurs wymaga, by najpierw ukończyć sam siebie, więc nigdy nie można go ukończyć.
Przykłady
- Wejście
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Wyjście
- true
- Wyjaśnienie
- Kurs 0 nie ma żadnych wymagań wstępnych, więc bierzesz go jako pierwszy. To odblokowuje kurs 1, który odblokowuje kursy 2 i 3, więc kolejność 0, 1, 2, 3 jest prawidłowa.
- Wejście
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Wyjście
- false
- Wyjaśnienie
- Kurs 0 czeka na 2, 2 czeka na 1, a 1 czeka na 0. Cała trójka czeka na siebie nawzajem w pętli, więc żaden z nich nie może zacząć.
Pytanie dodatkowe
Ile kursów zmieści się w jednym semestrze, o ile wymagania wstępne każdego kursu zostały spełnione w poprzednich semestrach? Ile semestrów wystarczy, by zrealizować wszystkie kursy?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Narysuj każdy kurs jako kropkę, a każdą parę
[a, b]jako strzałkę odbdoa. Jaki kształt na tym rysunku uniemożliwiłby ukończenie kursów?Pętla strzałek. Każdy kurs w pętli czeka na inny kurs z tej samej pętli, więc żaden z nich nie może być pierwszy. Pytanie brzmi, czy graf zawiera cykl.
Policz, na ile wymaganych wcześniej kursów każdy kurs jeszcze czeka. Utwórz kolejkę kursów, których licznik wynosi 0, a za każdym razem, gdy pobierzesz jeden z nich, zmniejsz licznik każdego kursu, który na niego czeka. Jeśli do kolejki trafi mniej niż
numCourseskursów, oznacza to, że istnieje cykl.
Rozwiązanie
Narysuj strzałkę b → a dla każdej pary [a, b]. Każdy kurs można ukończyć wtedy i tylko wtedy, gdy ten graf, mający V = numCourses węzłów i E = prerequisites.length strzałek, nie zawiera cyklu. Algorytm Kahna sprawdza to tak, jak planuje student: wciąż wybiera kurs, którego wymagania wstępne są spełnione, i sprawdza, czy uda się wybrać każdy kurs.
Bierz każdy darmowy kurs, runda po rundzie
Poprawne, ale nie kończy się na największych testach
Intuicja
W każdej rundzie wybierz każdy niewybrany kurs, którego wszystkie wymagania wstępne zostały spełnione. Zakończ, gdy runda nie wybierze żadnego kursu, i zwróć true, jeśli wybrano wszystkie kursy. Runda nie wybierze żadnego kursu tylko wtedy, gdy każdy pozostały kurs czeka na inny pozostały kurs, co oznacza cykl.
W każdej rundzie ponownie sprawdzasz każdą parę i każdy kurs, a możesz wybrać tylko jeden kurs. Łańcuch 5,001 kursów spośród 100,000 wymaga ponad 5,000 rund: około 5 × 10^8 sprawdzeń.
Algorytm
- Oznacz każdy kurs jako niezaliczony.
- Oznacz kurs jako zablokowany, jeśli jakaś para przypisuje mu niezaliczony warunek wstępny.
- Weź każdy kurs, który nie został ani zaliczony, ani zablokowany.
- Jeśli w tej rundzie niczego nie wzięto, zatrzymaj się; w przeciwnym razie wróć do kroku 2.
- Zwróć true, jeśli każdy kurs został zaliczony.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesPrzeszukiwanie w głąb z trzema stanami
Intuicja
Przeszukiwanie w głąb wykrywa cykl, śledząc ścieżkę, którą podąża. Przypisz każdemu kursowi jeden z trzech stanów: nieodwiedzony, na ścieżce, gotowy. Podążaj za strzałkami od kursu do kursów, które na niego czekają. Oznacz kurs jako znajdujący się na ścieżce, gdy do niego wchodzisz, a jako gotowy, gdy wszystkie jego strzałki zostaną sprawdzone.
Strzałka prowadząca do kursu znajdującego się na ścieżce zamyka pętlę: zwróć false. Strzałka prowadząca do gotowego kursu jest bezpieczna, ponieważ wszystko, co jest z niego osiągalne, zostało sprawdzone i nie zawiera cyklu, więc ponowne dotarcie do kursu samo w sobie nie oznacza cyklu. Każdy kurs jest odwiedzany raz, a każda strzałka śledzona raz: O(V + E).
Algorytm
- Utwórz dla każdego kursu listę kursów, które na niego czekają.
- Dla każdego nieodwiedzonego kursu oznacz go na ścieżce i umieść na stosie.
- Sprawdź szczyt stosu. Jeśli nie ma już żadnej strzałki, oznacz go jako ukończony i zdejmij ze stosu; w przeciwnym razie podążaj za następną strzałką.
- Jeśli strzałka prowadzi do kursu znajdującego się na ścieżce, zwróć false. Jeśli prowadzi do nieodwiedzonego kursu, oznacz ten kurs na ścieżce i umieść go na stosie.
- Gdy wszystkie kursy będą ukończone, zwróć true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueAlgorytm Kahna
Intuicja
Kurs staje się dostępny w chwili spełnienia ostatniego wymagania wstępnego. Dlatego śledź stopień wejściowy każdego kursu — liczbę wymagań wstępnych, na które nadal czeka — i umieść w kolejce wszystkie kursy, których licznik wynosi 0. Zaliczenie kursu zmniejsza licznik każdego kursu, który na niego czeka, a kurs, którego licznik spadnie do 0, trafia do kolejki. W pierwszym przykładzie liczniki wynoszą początkowo 0, 1, 1, 1: zaliczenie 0 udostępnia 1, a zaliczenie 1 udostępnia 2 i 3. Każdy kurs trafia do kolejki raz, a każda para zmniejsza jeden licznik raz: O(V + E).
Jeśli kolejka się opróżni, gdy kurs a nie został jeszcze zaliczony, jego licznik jest większy od 0, więc któreś wymaganie wstępne kursu a również nie zostało zaliczone i tak dalej. Taka wędrówka musi ponownie odwiedzić jakiś kurs: powstaje cykl. Z kolei każdy kurs w cyklu czeka na inny kurs z tego cyklu, więc żaden nie może być pierwszy. Kolejność, w jakiej kursy opuszczają kolejkę, stanowi prawidłowy harmonogram.
Algorytm
- Dla każdej pary [a, b] dodaj a do listy kursów, które czekają na b, i zwiększ stopień wejściowy a o 1.
- Umieść w kolejce każdy kurs o stopniu wejściowym równym 0.
- Wyjmij kurs z kolejki i go policz. Zmniejsz stopień wejściowy każdego kursu, który na niego czeka, i dodaj do kolejki każdy kurs, którego stopień wejściowy spadnie do 0.
- Gdy kolejka będzie pusta, zwróć informację, czy liczba kursów jest równa
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Pułapki i przypadki brzegowe
- Pomylenie kierunku.
[a, b]oznacza, że najpierw jest b: strzałka prowadzi od b do a, a stopień wejściowy a wzrasta. - Pomijanie kursów, które nie występują w żadnej parze. Przy
numCourses = 5i jedynej parze[4, 3]kursy 0, 1 i 2 również muszą od początku znaleźć się w kolejce. - Używanie dwóch stanów zamiast trzech w przeszukiwaniu w głąb. W rombie 0 → 1, 0 → 2, 1 → 3, 2 → 3 kurs 3 jest osiągany dwukrotnie i wygląda na cykl, jeśli śledzisz tylko elementy, które zostały „odwiedzone”.
- Rekurencja na łańcuchu 5,000 kursów: 5,000 wywołań w głąb, czyli więcej niż domyślny limit Pythona wynoszący 1,000.
- Zwracanie true po opróżnieniu kolejki bez sprawdzenia, czy ukończono
numCourseskursów. Drugi przykład zwróciłby true.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu Course Schedule?
O(V + E), gdzie V to liczba kursów, a E to liczba par. Można użyć algorytmu Kahna lub przeszukiwania w głąb. Każda para jest odczytywana raz, a każdy kurs jest przetwarzany raz. Listy i liczniki zajmują O(V + E) pamięci.
Czy w przypadku planu kursów należy użyć BFS czy DFS?
Oba działają w czasie O(V + E). Algorytm Kahna, czyli wersja z przeszukiwaniem wszerz, nie wymaga martwienia się o głębokość rekurencji i zwraca prawidłową kolejność kursów. Przeszukiwanie w głąb z trzema stanami to naturalny wybór, gdy trzeba również wskazać cykl, ponieważ tworzą go kursy znajdujące się na stosie.
Czym jest sortowanie topologiczne?
Kolejność węzłów grafu skierowanego, w której każda strzałka wskazuje do przodu; tutaj kolejność, w której każdy warunek wstępny występuje przed kursem, który go wymaga. Taka kolejność istnieje dokładnie wtedy, gdy graf nie zawiera cyklu, a kolejność, w której algorytm Kahna pobiera kursy, jest jedną z nich. Course Schedule pyta, czy taka kolejność istnieje.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def canFinish(numCourses, prerequisites):
# Wpisz kod tutajTest #1
Test #2
Argumenty
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Oczekiwany wynik
true