. La plupart des pierres supprimées avec la même ligne ou colonne

947. La plupart des pierres supprimées avec la même ligne ou colonne

Difficulté :Moyen

Sujets : Table de hachage, recherche en profondeur d'abord, recherche d'union, graphique

Sur un plan 2D, nous plaçons n pierres à des points de coordonnées entiers. Chaque point de coordonnées peut avoir au plus une pierre.

Une pierre peut être supprimée si elle partage soit la même ligne ou la même colonne qu'une autre pierre qui n'a pas été supprimée.

Étant donné un tableau de pierres de longueur n où pierres[i] = [xi, yi] représente l'emplacement de la i^ème pierre, renvoie le plus grand nombre possible de pierres pouvant être supprimées .

Exemple 1 :

• Entrée : pierres = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
• Sortie : 5
• Explication : Une façon de retirer 5 pierres est la suivante :
  1. Supprimez la pierre [2,2] car elle partage la même rangée que [2,1].
  2. Supprimez la pierre [2,1] car elle partage la même colonne que [0,1].
  3. Supprimez la pierre [1,2] car elle partage la même rangée que [1,0].
  4. Supprimez la pierre [1,0] car elle partage la même colonne que [0,0].
  5. Supprimez la pierre [0,1] car elle partage la même rangée que [0,0].
  6. La pierre [0,0] ne peut pas être supprimée car elle ne partage pas de ligne/colonne avec une autre pierre encore dans le plan.

Exemple 2 :

• Entrée : pierres = [[0,0],[0,2],[1,1],[2,0],[2,2]]
• Sortie : 3
• Explication : Une façon d'effectuer 3 mouvements est la suivante :
  1. Supprimez la pierre [2,2] car elle partage la même rangée que [2,0].
  2. Supprimez la pierre [2,0] car elle partage la même colonne que [0,0].
  3. Supprimez la pierre [0,2] car elle partage la même rangée que [0,0].
  4. Les pierres [0,0] et [1,1] ne peuvent pas être supprimées puisqu'elles ne partagent pas de ligne/colonne avec une autre pierre encore dans le plan.

Exemple 3 :

• Entrée : pierres = [[0,0]]
• Sortie : 0
• Explication : [0,0] est la seule pierre dans l'avion, vous ne pouvez donc pas la retirer.

Contraintes :

• 1 <= pierres.longueur <= 1000
• 0 <= x_i, y_i <= 10⁴
• Il n'y a pas deux pierres au même point de coordonnées.

Solution :

Nous pouvons mettre en œuvre la solution en utilisant une approche Depth-First Search (DFS). L’idée est de considérer les pierres reliées par des lignes ou des colonnes comme faisant partie du même composant connecté. Une fois que vous avez trouvé tous les composants connectés, le nombre maximum de pierres pouvant être supprimées est le nombre total de pierres moins le nombre de composants connectés.

Implémentons cette solution en PHP : 947. La plupart des pierres supprimées avec la même ligne ou colonne

  
  
  Explication:




Fonction DFS :


La fonction dfs est utilisée pour explorer toutes les pierres qui se trouvent dans le même composant connecté. Si une pierre est connectée (dans la même ligne ou colonne) à la pierre actuelle, nous effectuons récursivement DFS sur cette pierre.



Fonction principale :


Nous parcourons toutes les pierres, et pour chaque pierre qui n'a pas été visitée, nous effectuons un DFS pour marquer toutes les pierres dans le même composant connecté.
Nous comptons le nombre de composants connectés, et le résultat est le nombre total de pierres moins le nombre de composants connectés ($n - $numComponents).



Exemple d'exécution :


Pour le premier exemple, il trouve correctement que 5 pierres peuvent être retirées, laissant 1 pierre qui ne peut pas être retirée.





  
  
  Complexité:




Complexité temporelle : O(n^2) en raison des boucles imbriquées et du parcours DFS.

Complexité spatiale : O(n) pour stocker les pierres visitées.


Cette solution devrait fonctionner efficacement dans les limites données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!