. Diviser la liste chaînée en parties

725. Diviser la liste chaînée en parties

Difficulté :Moyen

Sujets : Liste chaînée

Étant donné la tête d'une liste chaînée unique et un entier k, divisez la liste chaînée en k parties de liste chaînée consécutives.

La longueur de chaque partie doit être aussi égale que possible : deux parties ne doivent pas avoir une taille différente de plus d'une. Cela peut conduire à ce que certaines parties soient nulles.

Les parties doivent être dans l'ordre d'apparition dans la liste d'entrée, et les parties apparaissant plus tôt doivent toujours avoir une taille supérieure ou égale aux parties apparaissant plus tard.

Renvoyer un tableau des k parties.

Exemple 1 :

• Entrée : tête = [1,2,3], k = 5
• Sortie : [[1],[2],[3],[],[]]
• Explication :
  • Le premier élément Output[0] a Output[0].val = 1, Output[0].next = null.
  • La sortie du dernier élément[4] est nulle, mais sa représentation sous forme de chaîne en tant que ListNode est [].

Exemple 2 :

• Entrée : tête = [1,2,3,4,5,6,7,8,9,10], k = 3
• Sortie : [[1,2,3,4],[5,6,7],[8,9,10]]
• Explication :
  • L'entrée a été divisée en parties consécutives avec une différence de taille d'au plus 1, et les parties antérieures sont d'une taille plus grande que les parties ultérieures.

Contraintes :

• Le nombre de nœuds dans la liste est compris entre [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

Indice :

1. S'il y a N nœuds dans la liste et k parties, alors chaque partie a N/k éléments, sauf que les N%k premières parties en ont un supplémentaire.

Solution :

L'observation clé est que le nombre de nœuds dans chaque partie ne doit pas différer de plus de 1. Cela signifie :

1. Calculez la longueur de la liste chaînée.
2. Déterminez la taille minimale de chaque pièce (part_size = length // k).
3. Répartissez les nœuds supplémentaires uniformément sur les premières parties (extra_nodes = length % k). Les premières parties extra_nodes doivent avoir chacune un nœud supplémentaire.

Approche

1. Calculer la longueur : Parcourez la liste chaînée pour trouver le nombre total de nœuds.
2. Déterminez la taille de chaque pièce :
   • Chaque partie doit avoir au moins une longueur // k nœuds.
   • Les parties % k de première longueur doivent avoir un nœud supplémentaire.
3. Diviser la liste : utilisez une boucle pour diviser la liste chaînée en k parties. Pour chaque partie :
   • S'il doit avoir des nœuds supplémentaires, attribuez part_size + 1 nœuds.
   • Sinon, attribuez des nœuds part_size.
4. Parties nulles : Si la liste est plus courte que k, certaines parties seront vides (nulles).

Implémentons cette solution en PHP : 725. Diviser la liste chaînée en parties

<?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>
  
  
  Explication:
</h3>

<ol>
<li><p><strong>Calculer la longueur</strong> : Nous parcourons d'abord la liste chaînée pour trouver sa longueur.</p></li>
<li>
<p><strong>Déterminer les pièces</strong> :</p>

<ul>
<li>Nous calculons part_size comme longueur // k, ce qui donne la taille minimale que chaque pièce devrait avoir.</li>
<li>Nous calculons extra_nodes comme longueur % k, ce qui donne le nombre de pièces qui devraient avoir un nœud supplémentaire.</li>
</ul>
</li>
<li>
<p><strong>Diviser la liste</strong> : Nous parcourons k parties et divisons la liste :</p>

<ul>
<li>Pour chaque pièce, attribuez part_size + 1 nœuds si elle doit avoir un nœud supplémentaire, sinon juste part_size.</li>
<li>A la fin de chaque partie, on rompt le lien avec le reste de la liste.</li>
</ul>
</li>
<li><p><strong>Gérer les parties nulles</strong> : S'il y a moins de nœuds que k, les parties restantes seront nulles (vides).</p></li>
</ol>

<h3>
  
  
  Cas de test
</h3>

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

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

• Exemple 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]]

Cette solution divise efficacement la liste chaînée en k parties avec une complexité temporelle de (O(n + k)), où n est la longueur de la liste.

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!