Kursplan IV

1462. Kursplan IV

Schwierigkeit:Mittel

Themen: Tiefensuche, Breitensuche, Diagramm, Topologische Sortierung

Es gibt insgesamt numCourses-Kurse, die Sie absolvieren müssen, beschriftet von 0 bis numCourses - 1. Sie erhalten eine Reihe von Voraussetzungen, wobei Voraussetzungen[i] = [a_i, b_i ] zeigt an, dass Sie den Kurs belegen müssen a_i zuerst, wenn Sie Kurs b_i belegen möchten.

• Zum Beispiel gibt das Paar [0, 1] an, dass Sie Kurs 0 belegen müssen, bevor Sie Kurs 1 belegen können.

Voraussetzungen können auch indirekter sein. Wenn Kurs A eine Voraussetzung für Kurs B und Kurs B eine Voraussetzung für Kurs C ist, dann ist Kurs A eine Voraussetzung für Kurs C.

Sie erhalten außerdem ein Array-Abfragen, wobei query[j] = [u_j, v_j]. Für die j^te Abfrage sollten Sie antworten, ob Kurs u_j eine Voraussetzung für Kurs v_j ist oder nicht.

Gibt eine boolesche Array-Antwort zurück, wobei Antwort[j] die Antwort auf die j^teAbfrage ist.

Beispiel 1:

• Eingabe: numCourses = 2, Voraussetzungen = [[1,0]], Abfragen = [[0,1],[1,0]]
• Ausgabe: [falsch, wahr]
• Erklärung: Das Paar [1, 0] gibt an, dass Sie Kurs 1 belegen müssen, bevor Sie Kurs 0 belegen können. Kurs 0 ist keine Voraussetzung für Kurs 1, aber das Gegenteil ist der Fall.

Beispiel 2:

• Eingabe: numCourses = 2, Voraussetzungen = [], Abfragen = [[1,0],[0,1]]
• Ausgabe: [false,false]
• Erklärung: Es gibt keine Voraussetzungen und jeder Kurs ist unabhängig.

Beispiel 3:

• Eingabe: numCourses = 3, Voraussetzungen = [[1,2],[1,0],[2,0]], Abfragen = [[1,0],[1,2]]
• Ausgabe: [true,true]

Einschränkungen:

• 2
• 0
• Voraussetzungen[i].length == 2
• 0 i, b_i
• a_i != b_i
• Alle Paare [a_i, b_i] sind einzigartig.
• Das Voraussetzungsdiagramm enthält keine Zyklen.
• 1 4
• 0 i, v_i
• u_i != v_i

Hinweis:

1. Stellen Sie sich vor, die Kurse wären Knoten eines Diagramms. Wir müssen ein Array isReachable[i][j] erstellen.
2. Starten Sie ein BFS für jeden Kurs i und weisen Sie für jeden Kurs j, den Sie besuchen, isReachable[i][j] = True zu.
3. Beantworten Sie die Abfragen aus dem isReachable-Array.

Lösung:

Wir können eine Grafikdarstellung und den Floyd-Warshall-Algorithmus verwenden, um zu berechnen, ob jeder Kurs von einem anderen Kurs aus erreichbar ist. Dieser Ansatz wird die erforderlichen Beziehungen effizient handhaben und es uns ermöglichen, die Fragen direkt zu beantworten.

Lassen Sie uns diese Lösung in PHP implementieren: 1462. Kursplan IV

<?php /**
 * @param Integer $numCourses
 * @param Integer[][] $prerequisites
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

$numCourses = 2;
$prerequisites = [[1,0]];
$queries = [[0,1],[1,0]];

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,true]

$numCourses = 2;
$prerequisites = [];
$queries = [[1,0],[0,1]]

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,false]

$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];

$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [true, true]
?>

Erläuterung:

1. Diagramminitialisierung:

   • Das 2D-Array $isReachable wird mit „false“ initialisiert, was bedeutet, dass zunächst kein Kurs von einem anderen aus erreichbar ist.

2. Direkte Voraussetzungen:

   • Wir füllen das Array $isReachable basierend auf den Voraussetzungen. Für jede Voraussetzung [a, b] muss Kurs a vor Kurs b belegt werden.

3. Floyd-Warshall-Algorithmus:

   • Dieser Algorithmus berechnet den transitiven Abschluss des Graphen.
   • Für jeden Zwischenkurs k prüfen wir, ob Kurs i von Kurs j bis k erreichbar ist. Wenn ja, markieren wir $isReachable[i][j] = true.

4. Abfrageauswertung:

   • Jede Abfrage [u, v] wird beantwortet, indem einfach der Wert von $isReachable[u][v] überprüft wird.

Komplexität:

• Zeitkomplexität:
  • Floyd-Warshall-Algorithmus: O(numCourses³)
  • Abfragen: O(queries.length)
  • Gesamt: O(numCourses³ query.length)
• Weltraumkomplexität:
  • Der vom $isReachable-Array verwendete Speicherplatz ist O(numCourses²).

Beispielhafte Vorgehensweise:

Eingang:

$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];

Ausführung:

1. Nach der Initialisierung des Diagramms:

   $isReachable = [
       [false, false, false],
       [false, false, true],
       [false, false, false]
   ];

1. Nach Floyd-Warshall:

   $isReachable = [
       [false, false, false],
       [true, false, true],
       [true, false, false]
   ];

1. Beantwortung von Fragen:
   • Abfrage [1, 0]: wahr
   • Abfrage [1, 2]: wahr

Ausgabe:

[true, true]

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonKursplan IV. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!