


. Die meisten Steine wurden mit derselben Zeile oder Spalte entfernt
Aug 30, 2024 am 06:37 AM947. Die meisten Steine wurden mit derselben Zeile oder Spalte entfernt
Schwierigkeit:Mittel
Themen: Hash-Tabelle, Tiefensuche, Union-Suche, Diagramm
Auf einer 2D-Ebene platzieren wir n Steine an einigen ganzzahligen Koordinatenpunkten. Jeder Koordinatenpunkt darf höchstens einen Stein haben.
Ein Stein kann entfernt werden, wenn er entweder die gleiche Zeile oder die gleiche Spaltemit einem anderen Stein hat, der nicht entfernt wurde.
Angesichts einer Reihe von Steinen der Länge n, wobei Steine[i] = [xi, yi] die Position des iten Steins darstellt, wird die größtmögliche Anzahl von Steinen zurückgegeben, die entfernt werden können .
Beispiel 1:
- Eingabe: Steine = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
- Ausgabe: 5
-
Erklärung: Eine Möglichkeit, 5 Steine zu entfernen, ist wie folgt:
- Entfernen Sie den Stein [2,2], da er sich in derselben Reihe wie [2,1] befindet.
- Stein [2,1] entfernen, da er dieselbe Spalte wie [0,1] hat.
- Entfernen Sie den Stein [1,2], da er sich in derselben Reihe wie [1,0] befindet.
- Stein [1,0] entfernen, da er dieselbe Spalte wie [0,0] hat.
- Stein [0,1] entfernen, da er sich in derselben Reihe wie [0,0] befindet.
- Stein [0,0] kann nicht entfernt werden, da er keine Reihe/Spalte mit einem anderen Stein teilt, der sich noch auf der Ebene befindet.
Beispiel 2:
- Eingabe: Steine = [[0,0],[0,2],[1,1],[2,0],[2,2]]
- Ausgabe: 3
-
Erklärung: Eine Möglichkeit, drei Züge auszuführen, ist wie folgt:
- Entfernen Sie den Stein [2,2], da er sich in derselben Reihe wie [2,0] befindet.
- Stein [2,0] entfernen, da er dieselbe Spalte wie [0,0] hat.
- Stein [0,2] entfernen, da er sich in derselben Reihe wie [0,0] befindet.
- Steine [0,0] und [1,1] können nicht entfernt werden, da sie keine Reihe/Spalte mit einem anderen Stein teilen, der sich noch auf der Ebene befindet.
Beispiel 3:
- Eingabe: Steine = [[0,0]]
- Ausgabe: 0
- Erklärung: [0,0] ist der einzige Stein im Flugzeug, Sie können ihn also nicht entfernen.
Einschränkungen:
- 1 <= Steine.Länge <= 1000
- 0 <= xi, yi <= 104
- Keine zwei Steine befinden sich am selben Koordinatenpunkt.
Lösung:
Wir können die Lösung mithilfe eines Depth-First Search (DFS)-Ansatzes implementieren. Die Idee besteht darin, Steine, die durch Reihen oder Spalten verbunden sind, als Teil derselben verbundenen Komponente zu betrachten. Sobald Sie alle verbundenen Komponenten gefunden haben, ist die maximale Anzahl an Steinen, die entfernt werden können, die Gesamtzahl der Steine abzüglich der Anzahl der verbundenen Komponenten.
Lassen Sie uns diese Lösung in PHP implementieren: 947. Die meisten Steine wurden mit derselben Zeile oder Spalte entfernt
<?php function removeStones($stones) { ... ... ... /** * go to ./solution.php */ } function dfs($stoneIndex, &$stones, &$visited) { ... ... ... /** * go to ./solution.php */ } // Example usage: $stones1 = array( array(0, 0), array(0, 1), array(1, 0), array(1, 2), array(2, 1), array(2, 2) ); echo removeStones($stones1); // Output: 5 $stones2 = array( array(0, 0), array(0, 2), array(1, 1), array(2, 0), array(2, 2) ); echo removeStones($stones2); // Output: 3 $stones3 = array( array(0, 0) ); echo removeStones($stones3); // Output: 0 ?>Erläuterung:
DFS-Funktion:
- Die dfs-Funktion wird verwendet, um alle Steine zu erkunden, die sich in derselben verbundenen Komponente befinden. Wenn ein Stein (in derselben Zeile oder Spalte) mit dem aktuellen Stein verbunden ist, führen wir rekursiv DFS für diesen Stein aus.
Hauptfunktion:
- Wir iterieren über alle Steine und führen für jeden Stein, der nicht besucht wurde, ein DFS durch, um alle Steine in derselben verbundenen Komponente zu markieren.
- Wir zählen die Anzahl der verbundenen Komponenten und das Ergebnis ist die Gesamtzahl der Steine minus der Anzahl der verbundenen Komponenten ($n - $numComponents).
Beispielausführung:
- Im ersten Beispiel wird richtigerweise festgestellt, dass 5 Steine entfernt werden können, sodass 1 Stein übrig bleibt, der nicht entfernt werden kann.
Komplexität:
- Zeitkomplexität: O(n^2) aufgrund der verschachtelten Schleifen und der DFS-Durchquerung.
- Raumkomplexität: O(n) zum Speichern besuchter Steine.
Diese Lösung sollte innerhalb der gegebenen Einschränkungen effizient funktionieren.
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:
- GitHub
Das obige ist der detaillierte Inhalt von. Die meisten Steine wurden mit derselben Zeile oder Spalte entfernt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Heißer Artikel

Hot-Tools-Tags

Heißer Artikel

Heiße Artikel -Tags

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

11 beste PHP -URL -Shortener -Skripte (kostenlos und Premium)

Arbeiten mit Flash -Sitzungsdaten in Laravel

Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests

Erstellen Sie eine React -App mit einem Laravel -Back -Ende: Teil 2, reagieren

Curl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIs

12 Beste PHP -Chat -Skripte auf Codecanyon
