Course Schedule
Es gibt numCourses Kurse, nummeriert von 0 bis numCourses-1. Jedes Paar [a, b] in prerequisites bedeutet, dass du Kurs b abschließen musst, bevor du mit Kurs a beginnst. Gib true zurück, wenn es eine Reihenfolge gibt, in der du alle Kurse abschließen kannst, und false, wenn es keine gibt.
Funktion
- numCoursesinteger
- die Anzahl der Kurse
- prerequisitesinteger-2d-array
- die Paare [a, b], wobei jedes bedeutet, dass Kurs b vor Kurs a kommt
- Gibt zurückboolean
- true, wenn jeder Kurs abgeschlossen werden kann, andernfalls false
Einschränkungen
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Für jedes Paar
[a, b]gilt0 ≤ a, b < numCourses. - Kein Paar kommt zweimal vor.
- Ein Paar kann denselben Kurs zweimal nennen,
[a, a]. Dieser Kurs setzt sich selbst voraus, daher kann er niemals belegt werden.
Beispiele
- Eingabe
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Ausgabe
- true
- Erklärung
- Kurs 0 hat keine Voraussetzungen, also belegst du ihn zuerst. Dadurch wird Kurs 1 frei, wodurch 2 und 3 frei werden, sodass die Reihenfolge 0, 1, 2, 3 funktioniert.
- Eingabe
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Ausgabe
- false
- Erklärung
- Kurs 0 wartet auf 2, 2 wartet auf 1 und 1 wartet auf 0. Die drei warten in einer Schleife aufeinander, sodass keiner von ihnen zuerst beginnen kann.
Weiterführende Frage
In ein Semester passen beliebig viele Kurse, solange die Voraussetzungen für jeden Kurs in früheren Semestern erfüllt wurden. Wie viele Semester sind mindestens nötig, um alle Kurse abzudecken?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Zeichne jeden Kurs als Punkt und jedes Paar
[a, b]als Pfeil vonbnacha. Welche Form in dieser Zeichnung würde es unmöglich machen, alle Kurse abzuschließen?Ein Kreis aus Pfeilen. Jeder Kurs in einem Kreis wartet auf einen anderen Kurs desselben Kreises, daher kann keiner von ihnen jemals zuerst beginnen. Die Frage ist, ob der Graph einen Zyklus enthält.
Zähle, auf wie viele Voraussetzungen jeder Kurs noch wartet. Beginne mit einer Warteschlange der Kurse, deren Anzahl 0 beträgt, und verringere jedes Mal, wenn du einen Kurs bearbeitest, die Anzahl aller Kurse, die auf ihn warten. Wenn weniger als
numCoursesKurse jemals in die Warteschlange gelangen, gibt es einen Zyklus.
Lösung
Zeichne für jedes Paar [a, b] einen Pfeil b → a. Jeder Kurs kann genau dann abgeschlossen werden, wenn dieser Graph mit V = numCourses Knoten und E = prerequisites.length Pfeilen keinen Zyklus enthält. Kahn’s Algorithmus überprüft das so, wie ein Student plant: Nimm immer einen Kurs, dessen Voraussetzungen erfüllt sind, und prüfe, ob alle Kurse belegt werden.
Absolviere jeden kostenlosen Kurs, Runde für Runde
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Nimm in jeder Runde jeden noch nicht belegten Kurs, dessen Voraussetzungen alle erfüllt sind. Beende den Vorgang, wenn in einer Runde kein Kurs belegt wird, und gib true zurück, wenn alle Kurse belegt wurden. In einer Runde wird nur dann kein Kurs belegt, wenn jeder noch übrige Kurs auf einen anderen noch übrigen Kurs wartet – das ist ein Zyklus.
In jeder Runde werden alle Paare und alle Kurse erneut durchlaufen, obwohl möglicherweise nur ein einziger Kurs belegt wird. Eine Kette aus 5.001 Kursen unter 100.000 Kursen benötigt über 5.000 Runden: etwa 5 × 10^8 Prüfungen.
Algorithmus
- Markiere jeden Kurs als nicht belegt.
- Markiere einen Kurs als blockiert, wenn ein Paar ihm eine noch nicht erfüllte Voraussetzung zuordnet.
- Belege jeden Kurs, der weder belegt noch blockiert ist.
- Wenn in der Runde kein Kurs belegt wurde, stoppe; andernfalls gehe zurück zu Schritt 2.
- Gib true zurück, wenn jeder Kurs belegt ist.
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 == numCoursesTiefensuche mit drei Zuständen
Idee
Die Tiefensuche findet einen Zyklus, indem sie den Pfad verfolgt, dem sie folgt. Weise jedem Kurs einen von drei Zuständen zu: nicht besucht, auf dem Pfad, erledigt. Folge den Pfeilen von einem Kurs zu den Kursen, die auf ihn warten. Markiere einen Kurs beim Betreten als „auf dem Pfad“ und als „erledigt“, wenn alle seine Pfeile untersucht wurden.
Ein Pfeil zu einem Kurs auf dem Pfad schließt eine Schleife: Gib false zurück. Ein Pfeil zu einem erledigten Kurs ist sicher, denn alles, was von ihm aus erreichbar ist, wurde überprüft und enthält keinen Zyklus. Ein Kurs, der zweimal erreicht wird, bildet also nicht von selbst einen Zyklus. Jeder Kurs wird einmal betreten und jedem Pfeil wird einmal gefolgt: O(V + E).
Algorithmus
- Erstelle für jeden Kurs die Liste der Kurse, die auf ihn warten.
- Markiere jeden noch nicht besuchten Kurs auf dem Pfad und lege ihn auf einen Stapel.
- Betrachte den obersten Eintrag des Stapels. Wenn kein Pfeil mehr übrig ist, markiere ihn als erledigt und nimm ihn vom Stapel; andernfalls folge seinem nächsten Pfeil.
- Führt der Pfeil zu einem Kurs auf dem Pfad, gib false zurück. Führt er zu einem noch nicht besuchten Kurs, markiere diesen Kurs auf dem Pfad und lege ihn auf den Stapel.
- Wenn alle Kurse erledigt sind, gib true zurück.
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 TrueKahns Algorithmus
Idee
Ein Kurs wird zu einem bestimmten Zeitpunkt verfügbar: wenn seine letzte Voraussetzung erfüllt ist. Behalte also für jeden Kurs seinen Eingangsgrad im Blick, also die Anzahl der Voraussetzungen, auf die er noch wartet, und starte eine Warteschlange mit jedem Kurs, dessen Anzahl 0 beträgt. Wenn du einen Kurs belegst, verringerst du die Anzahl jedes Kurses, der auf ihn wartet; erreicht eine Anzahl 0, kommt der Kurs in die Warteschlange. Im ersten Beispiel beginnen die Anzahlen bei 0, 1, 1, 1: Wenn du 0 belegst, wird 1 verfügbar, und wenn du 1 belegst, werden 2 und 3 verfügbar. Jeder Kurs kommt einmal in die Warteschlange, und jedes Paar verringert eine Anzahl einmal: O(V + E).
Wenn die Warteschlange leer ist, während Kurs a noch nicht belegt wurde, ist seine Anzahl größer als 0, also wurde auch eine Voraussetzung von a noch nicht belegt, und so weiter. Bei diesem Durchlauf muss ein Kurs erneut besucht werden: ein Zyklus. Umgekehrt wartet jeder Kurs in einem Zyklus auf einen anderen Kurs darin, daher kann keiner zuerst belegt werden. Die Reihenfolge, in der die Kurse die Warteschlange verlassen, ist ein gültiger Studienplan.
Algorithmus
- Füge für jedes Paar [a, b] a zur Liste der Kurse hinzu, die auf b warten, und erhöhe den Eingangsgrad von a um 1.
- Lege jeden Kurs mit Eingangsgrad 0 in eine Warteschlange.
- Nimm einen Kurs aus der Warteschlange und zähle ihn. Verringere den Eingangsgrad jedes Kurses, der auf ihn wartet, und füge jeden Kurs, der dadurch 0 erreicht, zur Warteschlange hinzu.
- Wenn die Warteschlange leer ist, gib zurück, ob die Anzahl gleich
numCoursesist.
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
Stolperfallen und Grenzfälle
- Die Richtung verwechseln.
[a, b]bedeutet, dass b zuerst kommt: Der Pfeil verläuft von b nach a, und der Eingangsgrad von a erhöht sich. - Kurse vergessen, die in keinem Paar vorkommen. Bei
numCourses = 5und dem einzelnen Paar[4, 3]müssen die Kurse 0, 1 und 2 ebenfalls in die Warteschlange. - Bei der Tiefensuche nur zwei statt drei Zustände verwenden. Im Diamanten 0 → 1, 0 → 2, 1 → 3, 2 → 3 wird Kurs 3 zweimal erreicht und sieht wie ein Zyklus aus, wenn du nur „gesehen“ nachverfolgst.
- Eine Kette aus 5.000 Kursen rekursiv durchlaufen: 5.000 Aufrufe tief, über Pythons Standardgrenze von 1.000 hinaus.
- true zurückgeben, wenn die Warteschlange leer ist, ohne zu prüfen, ob
numCoursesKurse besucht wurden. Das zweite Beispiel würde true zurückgeben.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität des Course-Schedule-Problems?
O(V + E), wobei V die Anzahl der Kurse und E die Anzahl der Paare ist, mit entweder Kahns Algorithmus oder Tiefensuche. Jedes Paar wird einmal gelesen und jeder Kurs einmal verarbeitet. Die Listen und Zähler benötigen O(V + E) Speicherplatz.
Solltest du für Course Schedule BFS oder DFS verwenden?
Beide laufen in O(V + E). Kahn's Algorithmus, die Breitensuche-Variante, hat keine Rekursionstiefe, um die du dir Sorgen machen musst, und liefert dir eine gültige Reihenfolge der Kurse. Die Tiefensuche mit drei Zuständen ist die naheliegende Wahl, wenn du auch den Zyklus melden musst, denn die Kurse auf ihrem Stapel bilden ihn.
Was ist eine topologische Sortierung?
Eine Anordnung der Knoten eines gerichteten Graphen, bei der jeder Pfeil nach vorne zeigt; hier eine Anordnung, in der jede Voraussetzung vor dem Kurs kommt, der sie benötigt. Sie existiert genau dann, wenn der Graph keinen Zyklus hat, und die Reihenfolge, in der Kahn's Algorithmus Kurse aufnimmt, ist eine solche Anordnung. Course Schedule fragt, ob eine solche Anordnung existiert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def canFinish(numCourses, prerequisites):
# Schreibe hier den CodeTest #1
Test #2
Argumente
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Erwartete Ausgabe
true