Leetcode 1171:从链表中删去总和值为零的连续节点(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1171:从链表中删去总和值为零的连续节点(超详细的解法!!!)

in leetcode with 0 comment

给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。

删除完毕后,请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

示例 1:

输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。

示例 2:

输入:head = [1,2,3,-3,4]
输出:[1,2,4]

示例 3:

输入:head = [1,2,3,-3,-2]
输出:[1] 

提示:

解题思路

首先不难想到暴力解法,我们可以遍历整个链表,将之前遍历的节点元素存储到一个栈里面,判断当前元素和栈中的所有元素之和有没有可能构成0,如果可以的话,我们只需要将这些能构成0的元素出栈即可。那么我们栈中存放的元素就是最后剩余的元素。

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        s = []
        while head:
            t, d = 0, []
            while s:
                x = s.pop()
                d.append(x)
                t += x
                if t + head.val == 0:
                    d = []
                    break
            else:
                s = d[::-1]
            if t + head.val != 0 and head.val != 0:
                s.append(head.val)
            head = head.next
            
        h = ListNode(-1)
        res = h
        for i in s:
            h.next = ListNode(i)
            h = h.next
        return res.next

这显然不是一个优秀的做法,因为对每个节点我们都需要和之前的所有元素进行判断是不是能构成0,所以算法的时间复杂度是O(n^2)

我们可以采用前缀和的思想,我们知道通过两个前缀和相减可以得到区间和。例如

1 2 3 4 5
  ↑   ↑
  i   j

此时preSum[i]=1+2=3,而preSum[j]=1+2+3+4=10,那么sum([i+1,j])=preSum[j]-preSum[i]=7。这是一个非常好的性质,我们可以通过一个字典存储每个前缀和对应的节点,如果有两个节点的前缀和相同,那么说明这个区间内的和是0,我们只需要将之前存储的节点(假设之前节点是node,当前节点是curnode.next=cur.next(就表示将这段区间删除了)。

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = du = ListNode(0)
        du.next = head
        preSum = 0
        seen = {}
        
        while cur:
            preSum += cur.val
            node = seen.get(preSum, cur)
            if preSum in seen:
                del seen[preSum]
            seen[preSum] = node
            node.next = cur = cur.next
        return du.next

但是这种思维存在一个陷阱

[1, 3, 2, -3, -2, 5, 100, -100, 1]
preSum: 1 4 6 3 1 6 106 6 7
        ↑       ↑
        i       j

首先我们注意到两个1,那么我们首先会删除这个区间中的元素,但是要注意的是此时这个区间[i,j]在字典seen中的值也应该删除(比如说6在两个1之间,但是6在后面也出现了,所以这两个1之间的6应该不存在)。

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = du = ListNode(0)
        du.next = head
        preSum = 0
        seen = {}
        
        while cur:
            preSum += cur.val
            node = seen.get(preSum, cur)
            if preSum in seen:
                cur = seen[preSum].next
                p = preSum + cur.val
                while p != preSum:
                    del seen[p]
                    cur = cur.next
                    p += cur.val
            seen[preSum] = node
            node.next = cur = cur.next
        return du.next

非常好的思路,这种解法的时间复杂度是O(n)

reference:

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/discuss/366319/JavaC%2B%2BPython-Greedily-Skip-with-HashMap

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses