。將鍊錶拆分為多個部分

WBOY
發布: 2024-09-08 12:31:03
原創
912 人瀏覽過

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

難度:

主題:連結清單

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

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

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

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

範例1:

. Split Linked List in Parts

  • 輸入: head = [1,2,3], k = 5
  • 輸出: [[1],[2],[3],[],[]]
  • 說明:
    • 第一個元素output[0]的output[0].val = 1,output[0].next = null。
    • 最後一個元素output[4]為null,但其作為ListNode的字串表示形式是[]。

範例2:

. Split Linked List in Parts

  • 輸入: 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中文網其他相關文章!

來源:dev.to
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板