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 Kurs a beginnen kannst. 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
- wahr, wenn jeder Kurs abgeschlossen werden kann, andernfalls falsch
Einschränkungen
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Jedes Paar
[a, b]erfüllt0 ≤ a, b < numCourses. - Kein Paar erscheint zweimal.
- Ein Paar kann denselben Kurs zweimal nennen,
[a, a]. Dieser Kurs benötigt sich selbst als Voraussetzung, 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, und Kurs 1 gibt sowohl 2 als auch 3 frei, daher funktioniert die Reihenfolge 0, 1, 2, 3.
- Eingabe
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Ausgabe
- false
- Erklärung
- Kurs 0 wartet auf 2, Kurs 2 wartet auf 1 und Kurs 1 wartet auf 0. Die drei warten in einer Schleife aufeinander, sodass keiner von ihnen der erste Kurs sein kann, den du belegst.
+20 versteckte Tests beim Einreichen
Weiterführende Frage
Beliebig viele Kurse passen in ein Semester, solange die Voraussetzungen jedes Kurses in früheren Semestern erfüllt wurden. Was ist die kleinste Anzahl von Semestern, in der alle Kurse absolviert werden können?
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 Kreislauf aus Pfeilen. Jeder Kurs in einem Kreislauf wartet auf einen anderen Kurs desselben Kreislaufs, sodass keiner von ihnen jemals zuerst an der Reihe sein kann. Die Frage ist, ob der Graph einen Zyklus enthält.
Zähle, auf wie viele Voraussetzungen jeder Kurs noch wartet. Beginne mit den Kursen, deren Anzahl 0 beträgt, eine Warteschlange und verringere jedes Mal, wenn du einen Kurs belegst, die Anzahl jedes Kurses, der auf ihn wartet. Wenn weniger als
numCoursesKurse jemals in die Warteschlange gelangen, gibt es einen Zyklus.
Lösung
Wandle die Paare in einen gerichteten Graphen mit V = numCourses Knoten und E = prerequisites.length Kanten um, mit einem Pfeil b → a für jedes Paar [a, b]. Genau dann können alle Kurse abgeschlossen werden, wenn dieser Graph keinen Zyklus enthält. Kahn's Algorithmus entscheidet das so, wie ein Student planen würde: Belege immer einen Kurs, dessen Voraussetzungen alle erfüllt sind, und prüfe, ob dir zuerst die Kurse oder die Möglichkeiten ausgehen.
Nimm jeden kostenlosen Kurs, Runde für Runde
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Plane so, wie es ein Student tun würde. Sieh dir in jeder Runde jeden Kurs an, den du noch nicht belegt hast. Wenn alle seine Voraussetzungen erfüllt sind, belege ihn. Wiederhole das, bis in einer Runde kein Kurs mehr belegt wird. Wenn bis dahin alle Kurse belegt sind, lautet die Antwort wahr.
Warum eine festgefahrene Runde falsch bedeutet: Wenn in einer Runde kein Kurs belegt wird, hat jeder noch offene Kurs eine Voraussetzung, die ebenfalls noch offen ist. Beginne bei einem beliebigen offenen Kurs und gehe immer weiter zu einer seiner noch nicht belegten Voraussetzungen. Dir gehen nie die Schritte aus, und es gibt nur eine begrenzte Anzahl von Kursen, also kommst du zu einem Kurs zurück, den du bereits besucht hast. Das ist ein Zyklus, und die Kurse darin warten für immer aufeinander.
Die Methode ist korrekt, aber in jeder Runde werden alle Paare und alle Kurse erneut durchgegangen, und in einer Runde kann nur ein einziger Kurs belegt werden. Eine Kette aus 5,001 Kursen, von denen jeder den vorherigen voraussetzt, benötigt mehr als 5,000 Runden; bei 100,000 Kursen sind das etwa 5 × 10^8 Prüfungen, von denen sich fast alle auf Kurse beziehen, deren Status sich nicht geändert hat.
Algorithmus
- Markiere jeden Kurs als nicht belegt.
- Markiere einen Kurs als blockiert, wenn ihm ein Paar eine noch nicht belegte Voraussetzung zuweist.
- Belege jeden Kurs, der weder belegt noch blockiert ist.
- Wenn die Runde nichts belegt hat, 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
Ein Zyklus ist ein Pfad, der zu seinem Ausgangspunkt zurückführt. Die Tiefensuche findet einen, indem sie sich merkt, welche Kurse sich gerade auf dem Pfad befinden, den sie entlanggeht. Weise jedem Kurs einen von drei Zuständen zu: nicht besucht, auf dem aktuellen Pfad und abgeschlossen.
Gehe von einem Kurs entlang seiner Pfeile zu den Kursen, die auf ihn warten. Markiere einen Kurs als „auf dem Pfad“, wenn du ihn betrittst, und als „abgeschlossen“, wenn jeder ausgehende Pfeil untersucht wurde und du zurückgehst. Ein Pfeil zu einem Kurs, der sich auf dem Pfad befindet, bedeutet, dass du im Kreis gelaufen bist: Gib false zurück. Ein Pfeil zu einem abgeschlossenen Kurs ist sicher, da alles, was von ihm aus erreichbar ist, überprüft wurde und keinen Zyklus enthält; überspringe ihn also. Jeder Kurs wird einmal betreten und jedem Pfeil wird einmal gefolgt.
Zwei Zustände reichen nicht aus. Bei der Raute 0 → 1, 0 → 2, 1 → 3, 2 → 3 erreicht die Suche Kurs 3 ein zweites Mal über 2, aber Kurs 3 ist bis dahin abgeschlossen und befindet sich nicht auf dem Pfad, und es gibt keinen Zyklus. Nur ein Pfeil zurück auf den aktuellen Pfad schließt eine Schleife.
Schreibe die Suche mit einem eigenen Stack und speichere für jeden Kurs die Position seines nächsten noch nicht untersuchten Pfeils. Die rekursive Version ist kürzer, aber eine Kette aus 5.000 Kursen würde 5.000 Aufrufe tief gehen.
Algorithmus
- Erstelle für jeden Kurs eine Liste der Kurse, die auf ihn warten.
- Markiere jeden noch nicht besuchten Kurs auf dem Pfad und lege ihn auf einen Stapel.
- Betrachte das oberste Element des Stapels. Wenn kein Pfeil mehr übrig ist, markiere es als erledigt und entferne es vom Stapel; andernfalls folge seinem nächsten Pfeil.
- Wenn der Pfeil zu einem Kurs auf dem Pfad führt, gib false zurück. Wenn er zu einem noch nicht besuchten Kurs führt, markiere diesen Kurs auf dem Pfad und lege ihn auf den Stapel.
- Wenn jeder Kurs erledigt ist, 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
Die Durchläufe im ersten Ansatz verschwenden Zeit damit, Kurse erneut zu überprüfen, die sich nicht geändert haben. Ein Kurs wird genau in einem Moment frei: wenn seine letzte Voraussetzung erfüllt ist. Zähle also für jeden Kurs, auf wie viele Voraussetzungen er noch wartet – seinen Eingangsgrad. Wenn du einen Kurs belegst, verringere den Zähler jedes Kurses, der auf ihn wartet. Fällt ein Zähler auf 0, ist dieser Kurs jetzt frei, also legst du ihn in eine Warteschlange.
Beginne die Warteschlange mit allen Kursen, deren Zähler von Anfang an 0 ist, und nimm dann Kurse aus der Warteschlange, bis sie leer ist. Im ersten Beispiel beginnen die Zähler für die Kurse 0 bis 3 mit 0, 1, 1, 1. Wenn du 0 belegst, sinkt der Zähler von Kurs 1 auf 0; wenn du 1 belegst, sinken die Zähler der Kurse 2 und 3 auf 0; alle vier werden belegt, also lautet die Antwort true. Jeder Kurs kommt höchstens einmal in die Warteschlange, und jedes Paar verringert einen Zähler genau einmal, daher beträgt der Aufwand O(V + E).
Warum ein übrig gebliebener Kurs einen Zyklus bedeutet: Wenn die Warteschlange leer ist, während Kurs a noch nicht belegt wurde, liegt sein Zähler über 0, also wurde auch eine seiner Voraussetzungen, b, noch nicht belegt. Dasselbe gilt für b und so weiter. Ein Weg von einem Kurs zu einer unbelegten Voraussetzung endet nie, also besucht er erneut einen Kurs – das ist ein Zyklus. Im zweiten Beispiel beginnt kein Zähler bei 0, die Warteschlange ist anfangs leer und keiner der drei Kurse wird belegt.
Auch die umgekehrte Richtung gilt: Ein Kurs in einem Zyklus wartet auf einen anderen Kurs desselben Zyklus, daher kann sein Zähler nicht auf 0 sinken, bevor jener belegt wird, und keiner von ihnen kommt jemals zuerst dran. „Jeder Kurs wird belegt“ und „Es gibt keinen Zyklus“ bedeuten also dasselbe. Als Bonus ist die Reihenfolge, in der die Kurse die Warteschlange verlassen, ein gültiger Stundenplan.
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, dessen Eingangsgrad dadurch 0 erreicht, zur Warteschlange hinzu.
- Wenn die Warteschlange leer ist, gib zurück, ob die Anzahl
numCoursesentspricht.
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 meisten Fehler entstehen durch eine vertauschte Richtung eines Paars, eine zu strenge Zyklusprüfung oder Kurse, die in keinem Paar vorkommen.
- Die Richtung verwechseln.
[a, b]bedeutet, dass b zuerst kommt. Der Pfeil verläuft also von b nach a, und der Eingangsgrad von a erhöht sich. Werden die Listen in eine Richtung aufgebaut und die Eingangsgrade in die andere Richtung gezählt, funktioniert der Algorithmus nicht. - Kurse vergessen, die in keinem Paar vorkommen. Bei
numCourses = 5und dem einzigen Paar[4, 3]zählen die Kurse 0, 1 und 2 trotzdem mit. Beginne die Warteschlange mit jedem Kurs, dessen Eingangsgrad 0 ist, nicht nur mit den Kursen, die in einem Paar vorkommen. - Ein Kurs ist seine eigene Voraussetzung,
[2, 2]. Das ist ein Zyklus der Länge eins: Sein Eingangsgrad erreicht nie 0 und das Ergebnis ist false. - Nur zwei statt drei Zustände bei der Tiefensuche verwenden. In der Raute 0 → 1, 0 → 2, 1 → 3, 2 → 3 wird Kurs 3 zweimal erreicht. Das sieht wie ein Zyklus aus, wenn du nur „gesehen“ nachverfolgst. Nur ein Pfeil zurück in den aktuellen Pfad schließt eine Schleife.
- Rekursion bei langen Ketten. Eine Kette aus 5.000 Kursen führt zu 5.000 Aufrufen Tiefe und überschreitet damit Pythons Standardlimit von 1.000.
- true zurückgeben, wenn die Warteschlange leer ist, ohne die Anzahl der belegten Kurse mit
numCourseszu vergleichen.
Häufige Fragen4
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, entweder mit Kahns Algorithmus oder mit Tiefensuche. Beim Erstellen der Listen wird jedes Paar einmal gelesen, jeder Kurs kommt höchstens einmal in die Warteschlange, und jedes Paar verringert einen Zähler einmal. Die Listen und Zähler benötigen O(V + E) Speicherplatz.
Warum bedeutet ein in Kahns Algorithmus übrig gebliebener Kurs, dass es einen Zyklus gibt?
Ein Kurs bleibt nur übrig, wenn seine Anzahl nie 0 erreicht hat, also bleibt auch mindestens eine seiner Voraussetzungen übrig. Verfolge dieses Warten von Kurs zu Kurs: Jeder Schritt führt zu einem weiteren übrig gebliebenen Kurs, und bei endlich vielen Kursen muss der Weg zu einem bereits besuchten Kurs zurückführen. Die Strecke zwischen den beiden Besuchen ist ein Zyklus.
Solltest du für die Kursplanung BFS oder DFS verwenden?
Beide laufen in O(V + E). Kahn-Algorithmus, die Breitensuche-Variante, hat keine Rekursionstiefe, um die man sich Sorgen machen müsste, und liefert dir kostenlos eine gültige Reihenfolge der Kurse. Die Tiefensuche mit drei Zuständen ist genauso schnell und die naheliegende Wahl, wenn du auch den Zyklus melden musst, denn die Kurse auf ihrem Stack bilden ihn.
Was ist eine topologische Sortierung?
Eine Anordnung der Knoten eines gerichteten Graphen, bei der jeder Pfeil nach vorne zeigt; hier eine Anordnung von Kursen, bei 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 auswählt, ist eine solche Anordnung. Course Schedule fragt, ob eine topologische Anordnung existiert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def canFinish(numCourses, prerequisites):
# Schreibe hier den CodeFall 1
Fall 2
Eingabe
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Erwartet
true