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

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 i^ten 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 <= x_i, y_i <= 10⁴
• 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:


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!