Échanges minimum pour regrouper tous ensemble II

2134. Échanges minimum pour regrouper tous les 1 ensemble II

Moyen

Un swap est défini comme prenant deux positions distinctes dans un tableau et en échangeant les valeurs qu'elles contiennent.

Un tableau circulaire est défini comme un tableau où l'on considère le premier élément et le dernier élément comme adjacent.

Étant donné un tableau circulaire binaire, renvoie le nombre minimum d'échanges requis pour regrouper tous les 1 présents dans le tableau à n'importe quel emplacement.

Exemple 1 :

• Entrée : nums = [0,1,0,1,1,0,0]
• Sortie : 1
• Explication : Voici quelques façons de regrouper tous les 1 :
  • [0,0,1,1,1,0,0] en utilisant 1 swap.
  • [0,1,1,1,0,0,0] en utilisant 1 échange.
  • [1,1,0,0,0,0,1] en utilisant 2 swaps (en utilisant la propriété circulaire du tableau).
  • Il n'y a aucun moyen de regrouper tous les 1 avec 0 swaps.
  • Ainsi, le nombre minimum de swaps requis est de 1.

Exemple 2 :

• Entrée : nums = [0,1,1,1,0,0,1,1,0]
• Sortie : 2
• Explication : Voici quelques façons de regrouper tous les 1 :
  • [1,1,1,0,0,0,0,1,1] en utilisant 2 swaps (en utilisant la propriété circulaire du tableau).
  • [1,1,1,1,1,0,0,0,0] en utilisant 2 swaps.
  • Il n'y a aucun moyen de regrouper tous les 1 avec 0 ou 1 swaps.
  • Ainsi, le nombre minimum d'échanges requis est de 2.

Exemple 3 :

• Entrée : nums = [1,1,0,0,1]
• Sortie : 0
• Explication : Tous les 1 sont déjà regroupés en raison de la propriété circulaire du tableau.
  • Ainsi, le nombre minimum d'échanges requis est de 0.

Contraintes :

• 1 <= nums.length <= 10⁵
• nums[i] vaut 0 ou 1.

Indice :

1. Remarquez que le nombre de 1 à regrouper est fixe. C'est le nombre de 1 que possède tout le tableau.
2. Appelez ce nombre au total. Nous devrions ensuite vérifier pour chaque sous-tableau de taille totale (éventuellement enroulé), combien d'échanges sont nécessaires pour que le sous-tableau soit composé uniquement de 1.
3. Le nombre d'échanges requis est le nombre de 0 dans le sous-tableau.
4. Pour éliminer la propriété circulaire du tableau, nous pouvons ajouter le tableau d'origine à lui-même. Ensuite, nous vérifions chaque sous-tableau de longueur totale.
5. Comment éviter de recompter à chaque fois le nombre de 0 dans le sous-tableau ? La technique de la fenêtre coulissante peut aider.

Solution :

Pour résoudre ce problème, nous pouvons suivre ces étapes :

1. Comptez le nombre total de 1 : Ce sera le nombre de 1 que nous devons regrouper.
2. Étendre le tableau : pour gérer la nature circulaire, ajoutez le tableau à lui-même.
3. Utiliser la technique de la fenêtre coulissante : appliquez la technique de la fenêtre coulissante sur le tableau étendu pour trouver le nombre minimum d'échanges requis.

Implémentons cette solution en PHP : 2134. Échanges minimum pour regrouper tous les 1 ensemble II

  
  
  Explication:




Comptez le nombre total de 1 : calculez le nombre total de 1 dans le tableau d'origine.

Étendre le tableau : concatène le tableau d'origine à lui-même pour gérer la nature circulaire.

Fenêtre initiale : Comptez le nombre de 0 dans la fenêtre initiale de taille égale au nombre total de 1.

Fenêtre coulissante : faites glisser la fenêtre sur le tableau étendu. Pour chaque nouvelle position, mettez à jour le nombre de 0 en fonction des éléments entrant et sortant de la fenêtre.

Trouver le minimum : Gardez une trace du nombre minimum de 0 rencontrés, qui correspond au nombre minimum d'échanges nécessaires.


Cette solution gère efficacement le tableau circulaire en le transformant en un problème linéaire et utilise la technique de la fenêtre glissante pour maintenir un nombre courant de 0 dans chaque fenêtre de taille égale au nombre total de 1.

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!