Mindestanzahl an Operationen, um alle Bälle in jede Box zu bewegen

1769. Mindestanzahl an Operationen, um alle Bälle in jede Box zu bewegen

Schwierigkeit:Mittel

Themen:Array, String, Präfixsumme

Sie haben n Boxen. Sie erhalten eine binäre Zeichenfolge „boxes“ der Länge n, wobei „boxes[i]“ „0“ ist, wenn das i^te Feld leer ist, und „1“, wenn es enthält einBall.

In einem Arbeitsgang können Sie einen Ball von einer Box in eine benachbarte Box bewegen. Box i grenzt an Box j an, wenn abs(i - j) == 1. Beachten Sie, dass sich danach möglicherweise mehr als eine Kugel in einigen Boxen befindet.

Gib eine Array-Antwort der Größe n zurück, wobei Antwort[i] die minimale Anzahl an Operationen ist, die erforderlich sind, um alle Kugeln in das i^teFeld zu bewegen.

Jede Antwort[i] wird unter Berücksichtigung des Ausgangszustands der Boxen berechnet.

Beispiel 1:

• Eingabe:boxen = "110"
• Ausgabe: [1,1,3]
• Erklärung: Die Antwort für jedes Feld lautet wie folgt:
  1. Erste Box: Sie müssen einen Ball in einem Arbeitsgang von der zweiten Box in die erste Box bewegen.
  2. Zweite Box: Sie müssen einen Ball in einem Arbeitsgang von der ersten Box in die zweite Box bewegen.
  3. Dritte Box: Sie müssen in zwei Schritten einen Ball von der ersten Box in die dritte Box und in einem Schritt eine Kugel von der zweiten Box in die dritte Box bewegen.

Beispiel 2:

• Eingabe:boxen = "001011"
• Ausgabe: [11,8,5,4,3,4]

Einschränkungen:

• n == boxen.length
• 1 <= n <= 2000
• boxen[i] ist entweder '0' oder '1'.

Hinweis:

1. Wenn Sie einen Ball von Box i nach Box j bewegen möchten, benötigen Sie Bauchmuskelbewegungen (i-j).
2. Um alle Bälle in eine Box zu verschieben, können Sie sie einzeln verschieben.
3. Iterieren Sie für jedes Feld i jede Kugel in einem Feld j und fügen Sie abs(i-j) zu den Antworten[i] hinzu.

Lösung:

Wir können einen Präfixsummenansatz verwenden, der es uns ermöglicht, die minimale Anzahl von Operationen zu berechnen, die erforderlich sind, um alle Bälle in jede Box zu bewegen, ohne jede Operation explizit zu simulieren.

Wichtige Beobachtungen:

1. Die Anzahl der Züge, die erforderlich sind, um einen Ball von Box i nach Box j zu bewegen, beträgt einfach abs(i - j).
2. Wir können die Gesamtzahl der Züge berechnen, um alle Bälle in eine bestimmte Box zu bewegen, indem wir die Positionen der Bälle und eine laufende Summe der Operationen nutzen.
3. Durch die Berechnung der Bewegungen von links nach rechts und von rechts nach links können wir das Ergebnis in zwei Durchgängen ermitteln.

Ansatz:

1. Links-nach-Rechts-Pass: Berechnen Sie bei diesem Pass die Anzahl der Züge, um alle Bälle von links beginnend in den aktuellen Strafraum zu bringen.
2. Rechts-nach-Links-Pass: Berechnen Sie bei diesem Pass die Anzahl der Züge, um alle Bälle von rechts beginnend in den aktuellen Strafraum zu bringen.
3. Kombinieren Sie die Ergebnisse beider Durchgänge, um das Endergebnis für jede Box zu erhalten.

Lösungsschritte:

1. Beginnen Sie damit, die Kästchenkette zu durchlaufen und zu zählen, wie viele Bälle sich links und rechts von jedem Kästchen befinden.
2. Berechnen Sie während der Iteration die Anzahl der Züge, die erforderlich sind, um alle Bälle in die aktuelle Box zu bringen, indem Sie sowohl die linken als auch die rechten Informationen verwenden.

Lassen Sie uns diese Lösung in PHP implementieren: 1769. Mindestanzahl an Operationen, um alle Bälle in jede Box zu bewegen

<?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>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<strong>Links-nach-rechts-Pass</strong>: Wir berechnen die Gesamtzahl der erforderlichen Vorgänge, um alle Bälle von der linken Seite in den aktuellen Strafraum zu bringen. Für jede gefundene Kugel ('1') aktualisieren wir die Gesamtzahl der Züge.</li>
<li>
<strong>Rechts-nach-Links-Pass</strong>: Ähnlich dem Links-nach-Rechts-Pass, aber wir berechnen die Anzahl der Vorgänge, um Bälle von der rechten Seite in den aktuellen Strafraum zu bewegen.</li>
<li>Die Gesamtzahl der Operationen für jede Box ist die Summe der Bewegungen aus dem linken und rechten Durchgang.</li>
</ol>

<h3>
  
  
  Beispielhafte Vorgehensweise:
</h3>

<h4>
  
  
  Beispiel 1:
</h4>



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

Ausgabe:

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

Beispiel 2:

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

Ausgabe:

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

Zeitkomplexität:

• Die Lösung wird in O(n) Zeit ausgeführt, da wir die Box-Zeichenfolge zweimal durchlaufen (einmal für den Durchlauf von links nach rechts und einmal für den Durchlauf von rechts nach links).
• Die Raumkomplexität beträgt O(n), da wir das Antwortarray speichern, um die Ergebnisse zu speichern.

Diese Lösung berechnet effizient die minimale Anzahl von Operationen für jedes Feld mithilfe der Präfixsummentechnik.

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 vonMindestanzahl an Operationen, um alle Bälle in jede Box zu bewegen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!