2024-05-06|閱讀時間 ‧ 約 24 分鐘

嵌套娃娃 用遞迴解 串列化簡題 Leetcode #2487

題目敘述

輸入給定一個鏈結串列的head node。

要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉


例如 5->2->13->3

5的右手邊有13,所以5刪除掉。

2的右手邊有13,所以2刪除掉。

13的右手邊沒有更大的節點,所以13留著。

3的右手邊沒有更大的節點,所以3留著。

最後輸出為13->3。


原本的英文題目敘述


測試範例

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

約束條件

 Constraints:

  • The number of the nodes in the given list is in the range [1, 10^5].

節點總數目介於 1 ~ 十萬之間。

  • 1 <= Node.val <= 10^5

每個節點的節點值也介於 1 ~ 十萬之間。


演算法 DFS遞迴解

這題的關鍵其實就隱藏在化簡規則裡。

題目說:
某個節點的右手邊只要有比較大的節點,就刪除掉


白話講,可以這麼說,通則就是

如果右邊有人比我(當下的節點)還大,則只保留右邊(相當於下個鄰居)

如果右邊沒有人比我大,則我自己保留下來,並且保留原本的連接


初始條件,也可以說 終止條件,什麼時候停下來?

當遇到空節點的時候,代表已經拜訪到串列的尾端,化簡流程結束


示意圖


程式碼 DFS遞迴解

class Solution:
def removeNodes(self, head):

## Base case:
# Empty node or empty list
if not head:
return head

## General cases:
# Use the same pattern to carry out reduction
head.next = self.removeNodes(head.next)

# Next neighbor is larger than me, then keep neighbor alive
if head.next and head.next.val > head.val:
return head.next
else:
# Next neighbor is smaller than or equal to me, then keep myself alive
return head



複雜度分析

時間複雜度: O(n)

線性掃描,從左到右掃描每個節點,總共耗時O(n)


空間複雜度: O(n)

線性掃描,從左到右掃描每個節點,遞迴call stack最大深度為O(n)


關鍵知識點

這題的關鍵其實就隱藏在化簡規則裡。

題目說:
某個節點的右手邊只要有比較大的節點,就刪除掉


白話講,可以這麼說,通則就是

如果右邊有人比我(當下的節點)還大,則只保留右邊(相當於下個鄰居)

如果右邊沒有人比我大,則我自己保留下來,並且保留原本的連接


Reference:

[1] Remove Nodes From Linked List - LeetCode

分享至
成為作者繼續創作的動力吧!
從 Google News 追蹤更多 vocus 的最新精選內容從 Google News 追蹤更多 vocus 的最新精選內容

作者的相關文章

小松鼠的演算法樂園 的其他內容

你可能也想看

發表回應

成為會員 後即可發表留言
© 2024 vocus All rights reserved.