1233. Unterordner aus dem Dateisystem entfernen

Schwierigkeit:Mittel

Themen: Array, String, Tiefensuche, Versuch

Geben Sie bei einer gegebenen Ordnerliste die Ordner zurück, nachdem Sie alle Unterordner in diesen Ordnern entfernt haben. Sie k?nnen die Antwort in beliebiger Reihenfolge zurücksenden.

Wenn sich ein Ordner[i] in einem anderen Ordner[j] befindet, wird er als Unterordner davon bezeichnet. Ein Unterordner von Ordner[j] muss mit Ordner[j] beginnen, gefolgt von einem ?/“. Beispielsweise ist ?/a/b“ ein Unterordner von ?/a“, aber ?/b“ ist kein Unterordner von ?/a/b/c“.

Das Format eines Pfads besteht aus einer oder mehreren verketteten Zeichenfolgen der Form: ?/“, gefolgt von einem oder mehreren englischen Kleinbuchstaben.

• Zum Beispiel sind ?/leetcode“ und ?/leetcode/problems“ gültige Pfade, eine leere Zeichenfolge und ?/“ hingegen nicht.

Beispiel 1:

• Eingabe: Ordner = ["/a",/a/b",/c/d",/c/d/e",/c/f"]
• Ausgabe: ["/a","/c/d","/c/f"]
• Erkl?rung: Der Ordner ?/a/b“ ist ein Unterordner von ?/a“ und ?/c/d/e“ befindet sich im Ordner ?/c/d“ in unserem Dateisystem.

Beispiel 2:

• Eingabe: Ordner = ["/a","/a/b/c","/a/b/d"]
• Ausgabe: ["/a"]
• Erkl?rung: Die Ordner ?/a/b/c“ und ?/a/b/d“ werden entfernt, da es sich um Unterordner von ?/a“ handelt.

Beispiel 3:

• Eingabe: Ordner = ["/a/b/c","/a/b/ca","/a/b/d"]
• Ausgabe: ["/a/b/c","/a/b/ca","/a/b/d"]

Einschr?nkungen:

• 1 <= Ordnerl?nge <= 4 * 10⁴
• 2 <= Ordner[i].L?nge <= 100
• Ordner[i] enth?lt nur Kleinbuchstaben und ?/“.
• Ordner[i] beginnt immer mit dem Zeichen ?/“.
• Jeder Ordnername ist einzigartig.

Hinweis:

1. Ordner lexikografisch sortieren.
2. Fügen Sie das aktuelle Element in ein Array ein und wiederholen Sie die Schleife, bis alle Unterordner entfernt sind. Wiederholen Sie dies, bis kein Element mehr übrig ist.

L?sung:

Wir k?nnen eine Kombination aus Sortierung und String-Vergleich verwenden. Die folgenden Schritte beschreiben eine L?sung in PHP:

1. Ordner lexikografisch sortieren: Durch das Sortieren der Ordnerpfade in lexikografischer Reihenfolge wird sichergestellt, dass jeder Unterordner sofort seinem übergeordneten Ordner folgt. Auf ?/a“ folgt beispielsweise in der sortierten Liste ?/a/b“, sodass wir problemlos nach Unterordnerbeziehungen suchen k?nnen.

2. Unterordner identifizieren und herausfiltern: Wir k?nnen die sortierte Liste durchlaufen und prüfen, ob der aktuelle Ordnerpfad ein Unterordner des zuvor hinzugefügten Pfads ist. Wenn ja, überspringen wir es. Wenn nicht, fügen wir es unserer Ergebnisliste hinzu.

3. Implementieren Sie die L?sung in PHP: Wir verfolgen den letzten zur Ergebnisliste hinzugefügten Ordnerpfad. Wenn der aktuelle Ordner mit diesem letzten Ordner beginnt und unmittelbar ein / folgt, handelt es sich um einen Unterordner und sollte ignoriert werden.

Lassen Sie uns diese L?sung in PHP implementieren: 1233. Unterordner aus dem Dateisystem entfernen

  
  
  Erl?uterung:



Sortierung: Die Funktion sort() ordnet Ordner in lexikografischer Reihenfolge an. Dies erleichtert das Auffinden von Unterordnerbeziehungen, da Unterordner direkt auf ihre übergeordneten Ordner folgen.

Durchlaufen Sie jeden Ordner:


Wenn das Ergebnis leer ist (erste Iteration) oder wenn der aktuelle Ordnerpfad nicht mit dem zuletzt hinzugefügten Ordner gefolgt von einem / beginnt, ist es kein Unterordner und wird dem Ergebnisarray hinzugefügt.
Wenn es mit dem letzten Ordnerpfad beginnt und unmittelbar darauf ein / folgt, handelt es sich um einen Unterordner und wir überspringen das Hinzufügen zum Ergebnis.


Ergebnis: Die Funktion gibt ein Ergebnis zurück, das nur die Stammordner enth?lt, ausgenommen etwaige Unterordner.


Dieser Ansatz ist effizient mit einer zeitlichen Komplexit?t von O(n log n) aufgrund des Sortierschritts und der lineare Scan hat O(n). ), was dies zu einer guten L?sung für gr??ere Eingaben innerhalb der Einschr?nkungen des Problems macht.

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 vonUnterordner aus dem Dateisystem entfernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!