通过递归获取嵌套列表的所有元素

Question

~ from This Edabit Challenge ~

我需要获得嵌套列表的所有元素，并使用递归将它们全部放在一个列表中。

下面的代码打印出每个元素，但是我如何将它们全部保存到一个列表并返回它们呢?

必须保持在函数的作用域中。我不能添加一个全局列表并附加它们。这在技术上是可行的，但对于我想要通过的挑战却行不通。

我输出了值(在代码中是var x)，因为这表明我正在接近(我认为)。我只需要一种方法将值返回给我的函数，并将其附加到我最终将返回的列表中。

例子:
flatten([[[[[["direction"], [372], ["one"], [[[[[["Era"]]]], "Sruth", 3337]]], "First"]]]]) ➞ ["direction", 372, "one", "Era", "Sruth", 3337, "First"]

flatten([[4666], [5394], [466], [[["Saskia", [[[[["DXTD"]], "Lexi"]]]]]]]) ➞ [4666, 5394, 466, "Saskia", "DXTD", "Lexi"]

代码:

<>以前def平(arr):Res = []如果isinstance(arr, list):对于我来说:res.append(平(我))其他:返回加勒比海盗如果isinstance(res, list):对于I in res:X = flatten(i)如果x:打印(x)x =平([[[[[["方向"],[372],[" "], [[[[[[" 时代"]]]],"Sruth",3337]]]",第一个"]]]])打印(主要)输出:

<>前方向372一个时代Sruth3337第一个[]上面的输出显示我的代码遍历了所有非列表值。

Answer 1

海武解法的变体…

它们的第一个解使用嵌套生成器，这意味着每个值都通过该生成器堆栈生成。如果结构是深度嵌套的，这可以使解决方案占用二次而不是线性时间。另一种方法是在主函数中创建一个本地列表，并让辅助函数填充它。我更喜欢使用嵌套函数，这样我就不必传递列表，也不必向外部暴露辅助函数。

def flatten(nested):
flat = []
def helper(nested):
for e in nested:
if isinstance(e, list):
helper(e)
else:
flat.append(e)
helper(nested)
return flat

深度为800的800个整数的基准测试:

26.03 ms  Hai_Vu
0.25 ms  Kelly
25.62 ms  Hai_Vu
0.24 ms  Kelly
26.07 ms  Hai_Vu
0.24 ms  Kelly

它们的第二个解使用"队列"(但实际上是把它当作"颠倒的")堆栈，仅在左侧扩展/弹出)。我认为普通的堆栈(使用列表)更自然，更简单:

def flatten(nested):
stack = [nested]
out = []
while stack:
e = stack.pop()
if isinstance(e, list):
stack += reversed(e)
else:
out.append(e)
return out

Answer 2

我想提供两种解决方案:第一种使用递归，第二种使用队列。

<标题>

def flatten_helper(nested):
for e in nested:
if isinstance(e, list):
yield from flatten_helper(e)
else:
yield e

def flatten(nested):
return list(flatten_helper(nested))

flatten_helper函数是一个生成器，它生成一个非列表元素的列表。如果一个元素是一个列表，我们再次调用flatten_helper，直到得到非列表元素。

<标题>第二方案

import collections
def flatten(nested):
queue = collections.deque(nested)
out = []
while queue:
e = queue.popleft()
if isinstance(e, list):
queue.extendleft(reversed(e))
else:
out.append(e)
return out

在这个解决方案中，我们循环遍历嵌套列表。如果元素是列表，则将每个子元素放入队列中，以供稍后处理。如果元素不是列表，则将其附加到out。

Answer 3

传递一个列表，并在每一步添加一个列表:

def flatten(arr, list_):
if isinstance(arr, list):
for i in arr:
flatten(i, list_)
else:
list_.append(arr)

test = [['a'], 'b']
output = []
flatten(test, output)
output
['a', 'b']

编辑:如果你特别想返回列表，使用

def flatten(arr, list_=None):
if list_ is None:
list_ = []
if isinstance(arr, list):
for i in arr:
flatten(i, list_)
else:
list_.append(arr)
return list_

Answer 4

另一种可能…海武第1溶液相同波长上的更多:

def flatter(lst):
output = []
for i in lst:
if isinstance(i, list):
output.extend(flatter(i))
else:
output.append(i)
return output