Nimm Geschenke vom reichsten Stapel

2558. Nimm Geschenke vom reichsten Stapel

Schwierigkeit:Einfach

Themen: Array, Heap (Prioritätswarteschlange), Simulation

Sie erhalten eine ganzzahlige Geschenkreihe, die die Anzahl der Geschenke in verschiedenen Stapeln angibt. Jede Sekunde machst du Folgendes:

• Wählen Sie den Stapel mit der maximalen Anzahl an Geschenken.
• Wenn es mehr als einen Stapel mit der maximalen Anzahl an Geschenken gibt, wählen Sie einen beliebigen aus.
• Lassen Sie den Boden der Quadratwurzel der Anzahl der Geschenke im Stapel zurück. Nimm den Rest der Geschenke.

Gib die Anzahl der nach k Sekunden verbleibenden Geschenke zurück.

Beispiel 1:

• Eingabe: Geschenke = [25,64,9,4,100], k = 4
• Ausgabe: 29
• Erklärung: Die Geschenke werden auf folgende Weise angenommen:
  • In der ersten Sekunde wird der letzte Stapel ausgewählt und 10 Geschenke bleiben zurück.
  • Dann wird der zweite Stapel ausgewählt und 8 Geschenke bleiben übrig.
  • Danach wird der erste Stapel ausgewählt und 5 Geschenke bleiben übrig.
  • Zuletzt wird der letzte Stapel noch einmal ausgewählt und 3 Geschenke bleiben übrig.
  • Die letzten verbleibenden Geschenke sind [5,8,9,4,3], die Gesamtzahl der verbleibenden Geschenke beträgt also 29.

Beispiel 2:

• Eingabe: Geschenke = [1,1,1,1], k = 4
• Ausgabe: 4
• Erklärung: In diesem Fall müssen Sie, egal für welchen Stapel Sie sich entscheiden, in jedem Stapel 1 Geschenk zurücklassen.
  • Das heißt, Sie können keinen Stapel mitnehmen.
  • Die Gesamtzahl der verbleibenden Geschenke beträgt also 4.

Einschränkungen:

• 1 <= Geschenke.Länge <= 10³
• 1 <= Geschenke[i] <= 10⁹
• 1 <= k <= 10³

Hinweis:

1. Wie können Sie den Überblick über die größten Geschenke im Sortiment behalten
2. Was ist ein effizienter Weg, die Quadratwurzel einer Zahl zu finden?
3. Können Sie die Werte der Geschenke fortlaufend addieren und gleichzeitig sicherstellen, dass sie in einer bestimmten Reihenfolge sind?
4. Können wir hier eine Prioritätswarteschlange oder einen Heap verwenden?

Lösung:

Wir können einen Max-Heap (Prioritätswarteschlange) verwenden, da wir wiederholt den Stapel mit der maximalen Anzahl an Geschenken auswählen müssen. Ein Max-Heap ermöglicht es uns, in konstanter Zeit effizient auf den größten Stapel zuzugreifen und den Heap zu aktualisieren, nachdem wir Geschenke vom Stapel genommen haben.

Ansatz:

1. Verwenden Sie einen Max-Heap:

   • Da wir immer wieder den Stapel mit der maximalen Anzahl an Geschenken erreichen müssen, ist ein Max-Heap (Prioritätswarteschlange) ideal. In PHP können wir SplPriorityQueue verwenden, eine Prioritätswarteschlange, die standardmäßig als Max-Heap funktioniert.
   • Um einen Max-Heap zu simulieren, fügen wir die Anzahl der Geschenke als negativen Wert ein, da SplPriorityQueue standardmäßig ein Min-Heap ist. Durch das Einfügen negativer Werte stellt der kleinste negative Wert die größte ursprüngliche Zahl dar.

2. Jede Sekunde verarbeiten:

   • Nehmen Sie jede Sekunde den Stapel mit der maximalen Anzahl an Geschenken vom Stapel.
   • Nehmen Sie alle Geschenke bis auf den Boden der Quadratwurzel der Anzahl der Geschenke in diesem Stapel.
   • Schieben Sie den modifizierten Stapel zurück in den Haufen.

3. Kündigung:

   • Wir hören nach k Sekunden auf oder sobald wir alle Sekunden verarbeitet haben.

Lassen Sie uns diese Lösung in PHP implementieren: 2558. Nimm Geschenke vom reichsten Stapel

<?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Heap-Initialisierung</strong>:</p>

<ul>
<li>
SplPriorityQueue wird verwendet, um einen Max-Heap zu simulieren. Mit der Einfügemethode können wir Elemente mit Priorität in den Heap verschieben.</li>
</ul>
</li>
<li>
<p><strong>Verarbeitung des größten Stapels</strong>:</p>

<ul>
<li>Für k-Iterationen wird der größte Stapel mit extract extrahiert.</li>
<li>Die Anzahl der zurückgelassenen Geschenke wird als Boden der Quadratwurzel des aktuell größten Stapels unter Verwendung von floor(sqrt(...)) berechnet.</li>
<li>Der reduzierte Stapel wird wieder in den Haufen eingefügt.</li>
</ul>
</li>
<li>
<p><strong>Verbleibende Geschenke summieren</strong>:</p>

<ul>
<li>Nach den k Operationen werden alle Elemente im Heap extrahiert und summiert, um die Gesamtzahl der verbleibenden Geschenke zu erhalten.</li>
</ul>
</li>
<li>
<p><strong>Edge Cases</strong>:</p>

<ul>
<li>Wenn Geschenke leer sind, ist das Ergebnis 0.</li>
<li>Wenn k größer als die Anzahl der möglichen Operationen ist, verarbeitet der Algorithmus dies ordnungsgemäß.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Zeitkomplexität:
</h3>

<ul>
<li>
<strong>Heap-Operationen (Einfügen und Extrahieren)</strong>: Jede Heap-Operation (Einfügen und Extrahieren) benötigt <em><strong>O(log n)</strong></em>, wobei <em><strong>n</strong></em> ist die Anzahl der Stapel.</li>
<li>
<strong>Durchlaufen von k Operationen</strong>: Wir führen <em><strong>k</strong></em> Operationen durch, die jeweils Heap-Extraktion und -Einfügung beinhalten und beide <em><strong>O(log n)</strong>.</em>
</li>

</ul>Die gesamte Zeitkomplexität beträgt also <p><em>O(k log n)<strong></strong>, wobei </em><em>n<strong></strong> die Anzahl der Stapel ist und </em><em>k<strong></strong> ist die Anzahl der Sekunden.</em>

</p>
  
  
  Beispielhafte Vorgehensweise:
<h3>

</h3>Zur Eingabe:<p>
<br></p>
<pre class="brush:php;toolbar:false"><?php
/**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. Zunächst hat die Prioritätswarteschlange die Stapel: [25, 64, 9, 4, 100].
2. Nach 1 Sekunde: Wählen Sie 100, lassen Sie 10 stehen. Die restlichen Geschenke sind: [25, 64, 9, 4, 10].
3. Nach 2 Sekunden: Wählen Sie 64, lassen Sie 8 stehen. Die restlichen Geschenke sind: [25, 8, 9, 4, 10].
4. Nach 3 Sekunden: Wählen Sie 25, lassen Sie 5 stehen. Die restlichen Geschenke sind: [5, 8, 9, 4, 10].
5. Nach 4 Sekunden: Wählen Sie 10, lassen Sie 3 stehen. Die restlichen Geschenke sind: [5, 8, 9, 4, 3].

Die Summe der verbleibenden Geschenke beträgt 5 8 9 4 3 = 29.

Dieser Ansatz löst das Problem mithilfe eines Max-Heaps effizient und funktioniert innerhalb der gegebenen Einschränkungen gut.

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 vonNimm Geschenke vom reichsten Stapel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!