Heim Backend-Entwicklung PHP-Tutorial . Die meisten Steine ​​wurden mit derselben Zeile oder Spalte entfernt

. Die meisten Steine ​​wurden mit derselben Zeile oder Spalte entfernt

Aug 30, 2024 am 06:37 AM

. Most Stones Removed with Same Row or Column

947. 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:
    1. Entfernen Sie den Stein [2,2], da er sich in derselben Reihe wie [2,1] befindet.
    2. Stein [2,1] entfernen, da er dieselbe Spalte wie [0,1] hat.
    3. Entfernen Sie den Stein [1,2], da er sich in derselben Reihe wie [1,0] befindet.
    4. Stein [1,0] entfernen, da er dieselbe Spalte wie [0,0] hat.
    5. Stein [0,1] entfernen, da er sich in derselben Reihe wie [0,0] befindet.
    6. 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:
    1. Entfernen Sie den Stein [2,2], da er sich in derselben Reihe wie [2,0] befindet.
    2. Stein [2,0] entfernen, da er dieselbe Spalte wie [0,0] hat.
    3. Stein [0,2] entfernen, da er sich in derselben Reihe wie [0,0] befindet.
    4. 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:

  1. 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.
  2. 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).
  3. 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:

  • LinkedIn
  • 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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße Artikel -Tags

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

11 beste PHP -URL -Shortener -Skripte (kostenlos und Premium) 11 beste PHP -URL -Shortener -Skripte (kostenlos und Premium) Mar 03, 2025 am 10:49 AM

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

Arbeiten mit Flash -Sitzungsdaten in Laravel Arbeiten mit Flash -Sitzungsdaten in Laravel Mar 12, 2025 pm 05:08 PM

Arbeiten mit Flash -Sitzungsdaten in Laravel

Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests Mar 12, 2025 pm 05:09 PM

Vereinfachte HTTP -Reaktion verspottet in Laravel -Tests

Einführung in die Instagram -API Einführung in die Instagram -API Mar 02, 2025 am 09:32 AM

Einführung in die Instagram -API

Erstellen Sie eine React -App mit einem Laravel -Back -Ende: Teil 2, reagieren Erstellen Sie eine React -App mit einem Laravel -Back -Ende: Teil 2, reagieren Mar 04, 2025 am 09:33 AM

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 Curl in PHP: So verwenden Sie die PHP -Curl -Erweiterung in REST -APIs Mar 14, 2025 am 11:42 AM

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

12 Beste PHP -Chat -Skripte auf Codecanyon 12 Beste PHP -Chat -Skripte auf Codecanyon Mar 13, 2025 pm 12:08 PM

12 Beste PHP -Chat -Skripte auf Codecanyon

Benachrichtigungen in Laravel Benachrichtigungen in Laravel Mar 04, 2025 am 09:22 AM

Benachrichtigungen in Laravel

See all articles