前往
大廳
主題

LeetCode - 725. Split Linked List in Parts 解題心得

Not In My Back Yard | 2022-03-13 00:00:10 | 巴幣 0 | 人氣 141

題目連結:


題目意譯:
給定一個單向的連結串列(Linked List)之頭 head 以及一整數 k,將該連結串列分為 k 個連續的連結串列之部分。

每個部分之長度應盡可能地相同:沒有兩個部分的長度差多於 1。這可能使得某些部分將為空。

每個部分應按照其在輸入列表中的順序出現,且每個先出現的部分應有著大小大於或等於後出現者的大小。

回傳一個含有 k 個部分的陣列。

限制:
列表中節點數位於範圍 [0, 1000] 中。
0 ≦ Node.val ≦ 1000
1 ≦ k ≦ 50



範例測資:
範例 1:
輸入: head = [1,2,3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
第一個元素 ouput[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,且先出現的部分之大小大於等於後出現的。


解題思維:
先掃過一次連結串列,得知其長度 L。接著我們計算出每個部分應至少有多少個節點,即 L ÷ k 取整數部分,餘數為 r。剩下的餘數 r 就平均分配到前 r 個部分(也就是前 r 個部分每個多得到一個節點)。

接著我們已知每個部分要有多少個節點,因此就再掃過一次連結串列並按照每個部分的節點數切分串列即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作