用java将列表扁平化

Question

我在一次面试中被问到这个问题

在java中给出一个假设的列表，该列表与保持整数内容一起，还可能包含另一个类似类型的列表。

示例：[1,3,5,[6,7],8,9,10,[11,13,15,[16,17,[18,19]]],20]

产出应是：

[1,3,5,6,7,8,9,10,11,13,15,16,17,18,19,20]

我想轻松点！所以我带了一个递归的解决方案来解决这个问题！还是不想？

面试官说，子列表可以下降到任何深度，因此可能导致堆叠溢出错误！

我试着想出一个非递归的解决方案，但是没有。有人能告诉我非递归解决方案可能是什么吗？

Answer 1

您可以使用LinkedList作为堆栈。

public static List<Object> flattenNonRecursive(List<Object> list) {
    List<Object> result = new ArrayList<>();
    LinkedList<Object> stack = new LinkedList<>(list);
    while (!stack.isEmpty()) {
        Object e = stack.pop();
        if (e instanceof List<?>)
            stack.addAll(0, (List<?>)e);
        else
            result.add(e);
    }
    return result;
}

public static List<Object> list(Object... args) {
    return Arrays.asList(args);
}

public static void main(String[] args) {
    List<Object> list = list(1, 3, 5, list(6, 7), 8, 9, 10, list(11, 13, 15, list(16, 17, list(18, 19))), 20);
    System.out.println("flatten=" + flattenNonRecursive(list));
}

结果

flatten=[1, 3, 5, 6, 7, 8, 9, 10, 11, 13, 15, 16, 17, 18, 19, 20]

Answer 2

下面是一个迭代Java实现(部分基于sarvesh的答案)：

import java.util.*;

import static java.util.Arrays.asList;

public class Main {
    public static void main(String[] ars) {
        List<Object> list = asList(asList(1, 2), 3, 4, asList(5, asList(6, 7)));

        System.out.println(flatten(list));
    }

    public static List<Integer> flatten(Iterable<Object> list) {
        List<Integer> result = new ArrayList<Integer>();
        Deque<Iterator> deque = new ArrayDeque<Iterator>();
        deque.add(list.iterator());

        while (!deque.isEmpty()) {
            Iterator it = deque.pop();

            while (it.hasNext()) {
                Object obj = it.next();
                if (obj instanceof Iterable) {
                    deque.push(it);
                    it = ((Iterable) obj).iterator();
                } else if (obj instanceof Integer) {
                    result.add((Integer) obj);
                }
            }
        }
        return result;
    }

}

Answer 3

您可以对列表中的每个元素使用DFS(深度优先搜索)过程。下面是来自wiki的示例代码

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)