我正在编写一个 Python 代码来删除链表中的那些连续元素,这些元素加起来为 0
链表定义如下:
class Node:
def __init__(self, val, next=None):
self.value = val
self.next = next
node = Node(10)
node.next = Node(5)
node.next.next = Node(-3)
node.next.next.next = Node(-3)
node.next.next.next.next = Node(1)
node.next.next.next.next.next = Node(4)
node.next.next.next.next.next.next = Node(-4)
从上面的数据来看,5 -> -3 -> -3 -> 1
和 4 -> -4
相加需要剔除到 0
。
遍历元素后,如
def removeConsecutiveSumTo0(node):
start = node
while start:
mod = False
total = 0
end = start
while end:
total += end.value
if total == 0:
start = end
mod = True
break
end = end.next
if mod == False:
res = start
start = start.next
return res
node = removeConsecutiveSumTo0(node)
while node:
print (node.value, end=' ')
node = node.next
# 10 (Expected output)
我无法创建包含加起来为 0
的连续元素的子集。因为它是一个 NP-Complete 问题
,如讨论的那样 here和 here .我如何设计算法来找到解决方案?
最佳答案
您可以尝试递归或嵌套循环,因为您应该在计算总和时尝试从每个节点开始。一个天真的实现可能如下所示:
def removeConsecutiveSumTo0(node):
start = node
while start.next:
total = 0
cur = start.next
while cur:
total += cur.value
if total == 0:
start.next = cur.next
break
cur = cur.next
else:
start = start.next
关于python - 如何删除链表中相加为0的连续元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57620642/