725。將鍊錶拆分為多個部分
難度:中
主題:連結清單
給定一個單鍊錶的頭和一個整數 k,將鍊錶分割成 k 個連續的鍊錶部分。
每個部分的長度應盡可能相等:任何兩個部分的尺寸不應相差超過一倍。這可能會導致某些部分為空。
各部分應按照輸入清單中出現的順序排列,且較早出現的部分的大小應始終大於或等於較晚出現的部分的大小。
傳回由 k 個部分組成的陣列。
範例1:
範例2:
約束:
提示:
解:
關鍵的觀察是每個部分的節點數不應相差超過 1。這意味著:
讓我們用 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)); } ?>
計算長度:我們先遍歷鍊錶求其長度。
確定零件:
分割清單:我們循環遍歷 k 個部分並分割清單:
處理空部分:如果節點數少於 k,則剩餘部分將為 null(空)。
$head = [1,2,3]; $k = 5; Output: [[1],[2],[3],[],[]]
$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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
以上是。將鍊錶拆分為多個部分的詳細內容。更多資訊請關注PHP中文網其他相關文章!