时间戳

首页 > 解决方案 > 解析“有序”列表并找到相应的和和加数的算法？

python - 解析“有序”列表并找到相应的和和加数的算法？

问题描述

抱歉，如果之前有人问过这个问题，但我已经搜索了好几天，但没有找到与我的问题相关的帮助。

我正在尝试研究的是一种解析列表（类似于预算表）并将索引分配给父母或孩子的方法。父级是其子级的总和，而子级是该父级（或没有父级的数字）的加数。

例如：[1,2,3,6]，其中 6 是 1、2 和 3 的父级。

或更复杂的例子[1,2,3,6,1,4,3,8,14,3,2,3,8,1,4,3,8,16,30]：

30 是这个列表的“根”，因为 30 = 14 + 16、14 = 6 + 8、6 = 1 + 2 + 3 等等。这个列表总是有点顺序的，即孩子总是一起出现在他们的父母之前（当然，当父母是另一位父母的孩子时除外）。我试图找到最有效的方法，我的 2 个解决方案使用堆栈，但它们并不是 100% 正确，因为上面的 2 个示例失败了。这是两者的伪代码：

解决方案尝试 1

stack = []
for number in list
    if stack.isEmpty()
        stack.push(number)
    elif stack.peek() > number
        stack.push(number)
    else
        copy = stack
        temp = []
        current = number
        while current > 0
            popped = copy.pop()
            temp.push(popped)
            current -= popped
        if current == 0
            while temp
                child = temp.pop()
                child.parent = number
            stack = copy
    stack.push(number)

解决方案尝试 2

stack = []
for number in list
    stack.push(number)

while stack.size() > 1
    child = stack.pop()
    copy = stack
    temp = []
    if child > stack.peek()
        while current > 0 and copy.size() > 0
            popped = copy.pop()
            temp.push(popped)
            current -= popped    
        if current == 0
            while temp
                child = temp.pop()
                child.parent = number

任何想法或想法将不胜感激。在这一点上，我正在用头撞墙。

编辑

复杂示例解决方案 [1,2,3,6,1,4,3,8,14,3,2,3,8,1,4,3,8,16,30]

                   30
            /             \
      14                     16
    /      \              /        \
  6          8           8             8
/  |  \   /  |  \     /  |   \     /   |   \
1  2   3  1  4   3   3   2    3   1    4    3

标签： pythonalgorithmlistsumstack

解决方案

这是一个有趣的问题。这是一个使用列表作为树的递归解决方案（根在索引 0，子在以下索引）：

def get_tree(nums, trees=None):
    trees = trees or []
    if not nums:
        return trees[0] if len(trees) == 1 else None
    val, *nums = nums
    for i in range(len(trees)):
        if val == sum(c[0] for c in trees[i:]):
            result = get_tree(nums,  trees[:i] + [[val] + trees[i:]])
            if result:
                return result
    return get_tree(nums, trees + [[val]])

print(get_tree([1, 2, 3, 6]))
print(get_tree([1, 2, 3, 6, 1, 4, 3, 8, 14, 3, 2, 3, 8, 1, 4, 3, 8, 16, 30]))
print(get_tree([1, 2, 3, 7]))
print(get_tree([1, 2, 3]))

# [6, [1], [2], [3]]
# [30, [14, [6, [1], [2], [3]], [8, [1], [4], [3]]], [16, [8, [3], [2], [3]], [8, [1], [4], [3]]]]
# None
# [3, [1], [2]]

的逻辑get_tree如下：

  • 您在迭代数字列表时收集树列表
  • 在 中的每个位置nums，您可以执行以下两项操作之一：
    • 取树列表末尾的任何树的后缀 ( trees[i:]) 并将它们作为子树放在以当前编号为根的新树下
    • 将当前数字作为新树添加到堆栈中
  • 当你到达列表的末尾并且堆栈上只有一棵树时，这就是结果

你基本上得到了一个后序遍历并从中生成所有可能的树，并在此过程中剔除那些总和不匹配的树。对于正整数，这个过程是确定性的，即要么只有一棵有效的树，要么没有。对于非正整数，可能有多个可能的有效树。一个简单的例子是一个只有零的列表，其中任何树都是有效的。

推荐阅读