2015-06-20 17 views
11

ich diese Frage in einem Interview gefragt wurdeeine Liste in java abflachen

Bei einer hypothetischen Liste in Java, die zusammen mit Halt integer Inhalts kann auch eine andere Liste ähnlicher Art halten

Beispiel:

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

ausgegeben werden soll

Einfach ich dachte! Also kam ich mit einer rekursiven Lösung, die das Problem löste! Oder nicht?

Der Interviewer sagte, dass Unterlisten in jede Tiefe gehen könnten und daher Stapelfehler verursachen könnten!

Ich versuchte, eine nicht rekursive Lösung zu finden, konnte aber nicht. Könnte jemand sagen, was nicht rekursive Lösung sein könnte?

+2

Wie wird diese Liste gespeichert? –

+0

Gute Frage, und ich denke, um das Problem zu beantworten, werden wir unsere eigenen Annahmen darüber machen müssen, wie diese Datenstruktur aussehen wird. –

+2

Mit rekursivem Code haben Sie immer die Möglichkeit eines Stack-Overflows, wenn die Rekursion zu tief geht, aber das ist in diesem Fall wirklich nur eine theoretische Möglichkeit - Sie müssen eine * sehr * tief verschachtelte Liste (tausende von Ebenen?) Haben Sie würden ein SOE in der Praxis bekommen. – Jesper

Antwort

10

Sie LinkedList als Stapel verwenden kann.

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)); 
} 

Ergebnis

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

Dies ist eine nette Lösung. Eine pedantische Anmerkung: Die LinkedList wird als * Stack * verwendet, nicht als Warteschlange. Überprüfen Sie auch [ArrayDeque] (https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html), das * push * - und * pop * -Methoden bereitstellt und normalerweise die Stack- und LinkedList-Leistung übertrifft Klassen, wenn sie so benutzt werden. – dnault

+0

nette Lösung, ist es! – Peps0791

+0

@dnault Ich sehe, was Sie sagen, aber es könnte ein wenig umständlich sein, den Inhalt einer Liste zum '0th' Index des ArrayDeque hinzuzufügen –

2

Sie können für jedes Element in der Liste die DFS-Prozedur (Depth First Search) verwenden. Im Folgenden finden Sie Beispielcode aus dem 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) 
+0

Ist eine typische dfs-Lösung nicht immer rekursiv? Und eine nicht rekursive Version von dfs wartet auf einen Binärbaum? – NwDev

+0

Es sieht so aus, aber es kann rekursiv geschrieben werden, https://en.wikipedia.org/wiki/Depth-first_search –

+0

Ein dfs kann nicht rekursiv sein und ein dfs (wie jede Suche) wird einen Baum bilden aber es wird selten binär –

4

Hier ist eine iterative Java-Implementierung (teilweise basierend auf Sarvesh Antwort):

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; 
    } 

} 
0

könnten Sie unten Art von Algorithmus verwenden

public List<?> flatten(List<?> source) { 
     List<?> currentSource = source; 
     List<Object> flattenedList = new ArrayList<Object>(); 
     boolean loop = true; 
     while (loop) { 
      loop = false; 
      for (Object item : currentSource) { 
       if (item instanceof Collection<?>) { 
        flattenedList.addAll((Collection<?>) item); 
        loop = true; 
       } else { 
        flattenedList.add(item); 
       } 
      } 
      if (loop) { 
       currentSource = flattenedList; 
       flattenedList = new ArrayList<Object>(); 
      } 
     } 

     return flattenedList; 
    }