Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2024/03/12 11:00)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串39/1548 (看更多)

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list 1171. Remove Zero Sum Consecutive Nodes from Linked List 給你一個鏈結串列，如果子串列相鄰元素和為0可以刪除這些節點，求出刪到最後的連結串列長什麼樣子。思路： 1.暴力法是透過維護一個list，每次加入元素i時都去檢查 sum(0, i-1), sum(0, i-2), sum(0, i-3), ... 如果和與元素 i 相加則把相關元素從尾端pop掉，最後把list的節點串在一起。 2.上面有很多重複計算的和，要多次求和可以往前綴和方面想，但要先考慮一下刪除中間的元素會不會對前綴和造成影響，考慮list=[7,10,-4,-6,4,-4] 整理出的前綴和 7 10 -4 -6 4 -4 sum 7 17 13 7 11 7 我們發現當sum重複出現時，中間的節點都可以刪除(中間和為0)，所以問題變成對每個節點尋找最右邊出現的相同和。 3.儲存最右元素的索引(next)可以使用map存，每次都更新成最新的，初始化的時候要放一個 0:dummy 的keyvalue，可以處理整個list和為0的情況。 pycode ------------------------------------------ class Solution: def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0, head) curr = head sum_map = {0: dummy} curr_sum = 0 while curr: curr_sum += curr.val sum_map[curr_sum] = curr curr = curr.next curr = dummy curr_sum = 0 while curr: curr_sum += curr.val curr.next = sum_map[curr_sum].next curr = curr.next return dummy.next ------------------------------------------ -- https://i.imgur.com/bFRiqA3.jpg