。リンクされたリストを部分的に分割する

725。リンクされたリストを部分に分割

難易度: 中

トピック: リンクされたリスト

単一リンク リストの先頭と整数 k を指定すると、リンク リストを k 個の連続するリンク リスト部分に分割します。

各パーツの長さはできる限り同じである必要があります。2 つのパーツのサイズが 1 つ以上異なることはできません。これにより、一部の部分が null になる可能性があります。

パーツは入力リスト内の出現順に並べる必要があり、先に出現するパーツのサイズは常に後から出現するパーツ以上のサイズである必要があります。

k 個の部分の配列を返します。

例 1:

• 入力: head = [1,2,3]、k = 5
• 出力: [[1],[2],[3],[],[]]
• 説明:
  • 最初の要素 Output[0] には、output[0].val = 1、output[0].next = null があります。
  • 最後の要素の出力[4]はnullですが、ListNodeとしての文字列表現は[]です。

例 2:

• 入力: head = [1,2,3,4,5,6,7,8,9,10]、k = 3
• 出力: [[1,2,3,4],[5,6,7],[8,9,10]]
• 説明:
  • 入力は、サイズの差が最大 1 である連続した部分に分割されており、前の部分のサイズが後の部分よりも大きくなります。

制約:

• リスト内のノードの数は [0, 1000] の範囲内です。
• 0
• 1

ヒント:

1. リストに N 個のノードと k 個のパーツがある場合、最初の N%k 個のパーツに追加の要素が含まれる場合を除き、すべてのパーツに N/k 個の要素があります。

解決策:

重要な点は、各パーツのノード数の差が 1 を超えてはいけないということです。これは次のことを意味します。

1. リンクされたリストの長さを計算します。
2. 各パートの最小サイズを決定します (part_size = length // k)。
3. 最初のいくつかの部分に追加のノードを均等に分散します (extra_nodes = length % k)。最初の extra_nodes 部分には、それぞれ 1 つの追加ノードが必要です。

アプローチ

1. 長さを計算する: リンクされたリストを走査して、ノードの合計数を見つけます。
2. 各パーツのサイズを決定します:
   各パートには少なくとも // k 個の長さのノードが必要です。
   最初の長さ % k の部分には 1 つの追加ノードが必要です。
3. リストの分割: ループを使用して、リンクされたリストを k 個の部分に分割します。各部分について:
   追加のノードが必要な場合は、part_size + 1 ノードを割り当てます。
   そうでない場合は、part_size ノードを割り当てます。
4. Null 部分: リストが k より短い場合、一部の部分は空 (null) になります。

このソリューションを PHP で実装してみましょう:

725。リンクされたリストを部分に分割

<?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));
}
?>

説明：

1. 長さの計算: まず、リンクされたリストを走査してその長さを見つけます。

2. パーツの決定:

   part_size を長さ // k として計算します。これにより、各パーツが持つ必要のある最小サイズが得られます。
   extra_nodes を長さ % k として計算します。これにより、1 つの追加ノードが必要なパーツの数が得られます。

3. リストの分割: k 個の部分をループしてリストを分割します:

   パーツごとに、追加のノードが必要な場合はpart_size + 1 ノードを割り当て、それ以外の場合はpart_size だけを割り当てます。
   各部分の最後で、リストの残りの部分へのリンクを解除します。

4. Null パーツの処理: ノードの数が k よりも少ない場合、残りのパーツは null (空) になります。

テストケース

• 例 1:

   $head = [1,2,3]; $k = 5;
   Output: [[1],[2],[3],[],[]]

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

このソリューションは、リンク リストを (O(n + k)) の時間計算量で k 個の部分に効率的に分割します。ここで、n はリストの長さです。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。リンクされたリストを部分的に分割するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。