. 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 entwederdie 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^tenSteins darstellt, wirddie 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

        
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 durch.
          
         
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 korrekterweise 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, demRepositoryeinen 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!