. Teilen Sie die verknüpfte Liste in Teile auf

725. Teilen Sie die verknüpfte Liste in Teile auf

Schwierigkeit:Mittel

Themen:Verknüpfte Liste

Angenommen der Kopf einer einfach verknüpften Liste und eine ganze Zahl k, teilen Sie die verknüpfte Liste in k aufeinanderfolgende verknüpfte Listenteile auf.

Die Länge jedes Teils sollte so gleich wie möglich sein: Keine zwei Teile sollten sich in der Größe um mehr als eins unterscheiden. Dies kann dazu führen, dass einige Teile null sind.

Die Teile sollten in der Reihenfolge ihres Vorkommens in der Eingabeliste vorliegen, und früher auftretende Teile sollten immer eine Größe haben, die größer oder gleich der später auftretenden Teile ist.

Gib ein Array der k Teile zurück.

Beispiel 1:

• Eingabe: head = [1,2,3], k = 5
• Ausgabe: [[1],[2],[3],[],[]]
• Erklärung:
  • Das erste Element Ausgabe[0] hat Ausgabe[0].val = 1, Ausgabe[0].next = null.
  • Die letzte Elementausgabe[4] ist null, aber ihre Zeichenfolgendarstellung als ListNode ist [].

Beispiel 2:

• Eingabe: head = [1,2,3,4,5,6,7,8,9,10], k = 3
• Ausgabe: [[1,2,3,4],[5,6,7],[8,9,10]]
• Erklärung:
  • Die Eingabe wurde in aufeinanderfolgende Teile mit einem Größenunterschied von höchstens 1 aufgeteilt, und frühere Teile sind größer als die späteren Teile.

Einschränkungen:

• Die Anzahl der Knoten in der Liste liegt im Bereich [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Hinweis:

1. Wenn es N Knoten in der Liste und k Teile gibt, dann hat jeder Teil N/k Elemente, außer dass die ersten N%k Teile ein zusätzliches haben.

Lösung:

Die wichtigste Beobachtung ist, dass sich die Anzahl der Knoten in jedem Teil nicht um mehr als 1 unterscheiden sollte. Das bedeutet:

1. Berechnen Sie die Länge der verknüpften Liste.
2. Bestimmen Sie die Mindestgröße jedes Teils (part_size = length // k).
3. Verteilen Sie die zusätzlichen Knoten gleichmäßig auf die ersten paar Teile (extra_nodes = Länge % k). Die ersten extra_nodes-Teile sollten jeweils einen zusätzlichen Knoten haben.

Ansatz

1. Berechnen Sie die Länge: Durchlaufen Sie die verknüpfte Liste, um die Gesamtzahl der Knoten zu ermitteln.
2. Bestimmen Sie die Größe jedes Teils:
   • Jeder Teil sollte mindestens // k Knoten lang sein.
   • Die ersten % k Teile der Länge sollten einen zusätzlichen Knoten haben.
3. Liste aufteilen: Verwenden Sie eine Schleife, um die verknüpfte Liste in k Teile aufzuteilen. Für jeden Teil:
   • Wenn es zusätzliche Knoten haben soll, weisen Sie part_size + 1 Knoten zu.
   • Wenn nicht, weisen Sie part_size-Knoten zu.
4. Nullteile: Wenn die Liste kürzer als k ist, sind einige Teile leer (null).

Lassen Sie uns diese Lösung in PHP implementieren: 725. Teilen Sie die verknüpfte Liste in Teile auf

<?php
// Definition for singly-linked list.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
 /**
 * @param ListNode $head
 * @param Integer $k
 * @return ListNode[]
 */
function splitListToParts($head, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to create a linked list from an array
function createLinkedList($arr) {
    $head = new ListNode($arr[0]);
    $current = $head;
    for ($i = 1; $i < count($arr); $i++) {
        $current->next = new ListNode($arr[$i]);
        $current = $current->next;
    }
    return $head;
}

// Helper function to print a linked list
function printList($head) {
    $result = [];
    while ($head !== null) {
        $result[] = $head->val;
        $head = $head->next;
    }
    return $result;
}

// Test case 1
$head = createLinkedList([1, 2, 3]);
$k = 5;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}

// Test case 2
$head = createLinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
$k = 3;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}
?>




<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li><p><strong>Länge berechnen</strong>: Wir durchlaufen zunächst die verknüpfte Liste, um ihre Länge zu ermitteln.</p></li>
<li>
<p><strong>Teile bestimmen</strong>:</p>

<ul>
<li>Wir berechnen part_size als Länge // k, was die Mindestgröße angibt, die jedes Teil haben sollte.</li>
<li>Wir berechnen extra_nodes als Länge % k, was die Anzahl der Teile angibt, die einen zusätzlichen Knoten haben sollten.</li>
</ul>
</li>
<li>
<p><strong>Liste aufteilen</strong>: Wir durchlaufen k Teile und teilen die Liste auf:</p>

<ul>
<li>Weisen Sie für jedes Teil part_size + 1 Knoten zu, wenn es einen zusätzlichen Knoten haben soll, andernfalls nur part_size.</li>
<li>Am Ende jedes Teils trennen wir die Verbindung zum Rest der Liste.</li>
</ul>
</li>
<li><p><strong>Null-Teile behandeln</strong>: Wenn es weniger Knoten als k gibt, sind die verbleibenden Teile null (leer).</p></li>
</ol>

<h3>
  
  
  Testfälle
</h3>

<ul>
<li>
<strong>Beispiel 1</strong>:
</li>
</ul>

<pre class="brush:php;toolbar:false">   $head = [1,2,3]; $k = 5;
   Output: [[1],[2],[3],[],[]]

• Beispiel 2:

   $head = [1,2,3,4,5,6,7,8,9,10]; $k = 3;
   Output: [[1,2,3,4],[5,6,7],[8,9,10]]

Diese Lösung teilt die verknüpfte Liste effizient in k Teile mit einer zeitlichen Komplexität von (O(n + k)) auf, wobei n die Länge der Liste ist.

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 von. Teilen Sie die verknüpfte Liste in Teile auf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!