Nombre minimum d'opérations pour déplacer toutes les balles vers chaque case

1769. Nombre minimum d'opérations pour déplacer toutes les balles vers chaque boîte

Difficulté :Moyen

Sujets : Tableau, chaîne, somme de préfixe

Vous avez n cases. Vous recevez une chaîne binaire boxes de longueur n, où boxes[i] vaut '0' si la i^ième case est vide, et '1' si elle contient une balle.

En une seule opération, vous pouvez déplacer une balle d'une case vers une case adjacente. La case i est adjacente à la case j si abs(i - j) == 1. Notez qu'après cela, il peut y avoir plus d'une balle dans certaines cases.

Renvoyer une réponse de tableau de taille n, où réponse[i] est le nombre minimum d'opérations nécessaires pour déplacer toutes les boules vers la i^ième case.

Chaque réponse[i] est calculée en considérant l'état initial des cases.

Exemple 1 :

• Saisie : cases = "110"
• Sortie : [1,1,3]
• Explication : La réponse pour chaque case est la suivante :
  1. Première case : vous devrez déplacer une balle de la deuxième case à la première case en une seule opération.
  2. Deuxième case : vous devrez déplacer une balle de la première case à la deuxième case en une seule opération.
  3. Troisième case : vous devrez déplacer une boule de la première case à la troisième case en deux opérations, et déplacer une boule de la deuxième case à la troisième case en une seule opération.

Exemple 2 :

• Saisie : cases = "001011"
• Sortie : [11,8,5,4,3,4]

Contraintes :

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] est soit « 0 », soit « 1 ».

Indice :

1. Si vous souhaitez déplacer une balle de la case i à la case j, vous aurez besoin de mouvements abdominaux (i-j).
2. Pour déplacer toutes les balles vers une boîte, vous pouvez les déplacer une par une.
3. Pour chaque case i, itérez sur chaque balle dans une case j et ajoutez abs(i-j) aux réponses[i].

Solution :

Nous pouvons utiliser une approche somme de préfixe qui nous permet de calculer le nombre minimum d'opérations nécessaires pour déplacer toutes les balles vers chaque boîte sans simuler explicitement chaque opération.

Observations clés :

1. Le nombre de mouvements requis pour déplacer une balle de la case i à la case j est simplement abs(i - j).
2. Nous pouvons calculer le nombre total de mouvements pour déplacer toutes les balles vers une boîte particulière en tirant parti des positions des balles et d'un total cumulé d'opérations.
3. En calculant les mouvements de gauche à droite et de droite à gauche, nous pouvons déterminer le résultat en deux passes.

Approche:

1. Passe de gauche à droite : Dans cette passe, calculez le nombre de mouvements pour amener toutes les balles dans la case actuelle en commençant par la gauche.
2. Passe de droite à gauche : Dans cette passe, calculez le nombre de mouvements pour amener toutes les balles dans la case actuelle en commençant par la droite.
3. Combinez les résultats des deux passes pour obtenir le résultat final pour chaque case.

Étapes de la solution :

1. Commencez par parcourir la chaîne de cases et comptez combien de balles se trouvent à gauche et à droite de chaque case.
2. Pendant l'itération, calculez le nombre de mouvements nécessaires pour amener toutes les balles dans la case actuelle en utilisant à la fois les informations gauche et droite.

Implémentons cette solution en PHP : 1769. Nombre minimum d'opérations pour déplacer toutes les balles vers chaque boîte

<?php
/**
 * @param String $boxes
 * @return Integer[]
 */
function minOperations($boxes) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$boxes = "110";
print_r(minOperations($boxes)); // Output: [1,1,3]

$boxes = "001011";
print_r(minOperations($boxes)); // Output: [11,8,5,4,3,4]
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<strong>Passe de gauche à droite</strong> : On calcule le nombre total d'opérations nécessaires pour amener toutes les balles du côté gauche vers la surface actuelle. Pour chaque balle trouvée (« 1 »), nous mettons à jour le nombre total de coups.</li>
<li>
<strong>Passe de droite à gauche</strong> : Semblable à la passe de gauche à droite, mais on calcule le nombre d'opérations pour déplacer les balles du côté droit vers la case actuelle.</li>
<li>Le nombre total d'opérations pour chaque case est la somme des mouvements des passes gauche et droite.</li>
</ol>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<h4>
  
  
  Exemple 1 :
</h4>



<pre class="brush:php;toolbar:false">$boxes = "110";
print_r(minOperations($boxes));

Sortie :

Array
(
    [0] => 1
    [1] => 1
    [2] => 3
)

Exemple 2 :

$boxes = "001011";
print_r(minOperations($boxes));

Sortie :

Array
(
    [0] => 11
    [1] => 8
    [2] => 5
    [3] => 4
    [4] => 3
    [5] => 4
)

Complexité temporelle :

• La solution s'exécute en temps O(n) car nous parcourons deux fois la chaîne de boîtes (une fois pour le passage de gauche à droite et une fois pour le passage de droite à gauche).
• La complexité spatiale est O(n) car nous stockons le tableau de réponses pour contenir les résultats.

Cette solution calcule efficacement le nombre minimum d'opérations pour chaque boîte en utilisant la technique de la somme des préfixes.

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!