。將鍊錶拆分為多個部分

725。將鍊錶拆分為多個部分

難度：中

主題：連結清單

給定一個單鍊錶的頭和一個整數 k，將鍊錶分割成 k 個連續的鍊錶部分。

每個部分的長度應盡可能相等：任何兩個部分的尺寸不應相差超過一倍。這可能會導致某些部分為空。

各部分應按照輸入清單中出現的順序排列，且較早出現的部分的大小應始終大於或等於較晚出現的部分的大小。

傳回由 k 個部分組成的陣列。

範例1：

• 輸入： head = [1,2,3], k = 5
• 輸出： [[1],[2],[3],[],[]]
• 說明：
  • 第一個元素output[0]的output[0].val = 1，output[0].next = null。
  • 最後一個元素output[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. 計算長度：遍歷鍊錶，求節點總數。
2. 確定各部分的大小：
   • 每個部分應該至少有長度 // k 個節點。
   • 第一個長度 % k 的部分應該有一個額外的節點。
3. 拆分清單：使用循環將鍊錶拆分為 k 部分。對於每個部分：
   • 如果應該有額外的節點，則分配part_size + 1個節點。
   • 如果沒有，則分配part_size節點。
4. 空部分：如果列表短於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，這給出了應該有一個額外節點的部分的數量。

3. 分割清單：我們循環遍歷 k 個部分並分割清單：

   • 對於每個部分，如果應該有額外的節點，則分配part_size + 1個節點，否則只分配part_size。
   • 在每個部分的末尾，我們斷開與清單其餘部分的連結。

4. 處理空部分：如果節點數少於 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]]

此解有效地將鍊錶分割為 k 個部分，時間複雜度為 (O(n + k))，其中 n 是清單的長度。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。將鍊錶拆分為多個部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！