Arraylist, List

Question

Wenn ich versuche Teilmenge Problem zu lösen, schreibe ich einen Code wie folgt aus:

public class Subsets { 
     public List<List<Integer>> subsets(int[] nums) { 
      List<List<Integer>> list = new ArrayList<>(); 
      Arrays.sort(nums); 
      backtrack(list, new ArrayList<>(), nums, 0); 
      return list; 
     } 
     public void backtrack(List<List<Integer>> list, ArrayList<Integer>temp, int[] nums, int start){ 
      list.add(temp); 
      for(int i = start; i<nums.length;i++){ 
       temp.add(nums[i]); 
       backtrack(list, temp, nums, i++); 
       temp.remove(temp.size()-1); 
      }   
     } 
    } 

Der Ausgang ist

[[], [], [], [] , [], [], [], []]

aber die richtige Antwort sollte

[[3] sein, [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]

Wenn ich den "Backtrack" ändere Code wie das, ist die Antwort richtig:

public void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, int start){ 
    list.add(new ArrayList(temp)); 
    for(int i = start; i<nums.length;i++){ 
    temp.add(nums[i]); 
    backtrack(list, temp, nums, i+1); 
    temp.remove(temp.size()-1); 
    } 
} 

Meine Frage: warum muss ich Code so schreiben:

public void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, int start){ 
     list.add(new ArrayList(temp)); 

statt, dass:

public void backtrack(List<List<Integer>> list, ArrayList<Integer> temp, int[] nums, int start){ 
     list.add(temp); 

Answer 1

H ere:

list.add(new ArrayList(temp)); 

, die ein neue List-Objekt erstellt, mit dem Inhalt der temp bei diesen Zeitpunkt.

Während

list.add(temp); 

fügt nur einen Verweis auf die bestehenden temp Liste list.

Also, im zweiten Fall, wenn Sie spätertemp ändern, die auch den Inhalt von list auswirkt.

Aber darüber hinaus: Sie Code ist viel schwieriger zu lesen/zu verstehen, wie es sein sollte. Es gibt keine Punkt in der Verwendung eines temp Parameter für diese Methode. Sie könnten beispielsweise temp eine lokale Variable innerhalb der Methode machen. Die eingehende Liste ist leer sowieso. Sie gewinnen nichts, wenn Sie dies zu einem Eingabeparameter machen. Sie fügen nur Verwirrung hinzu.

Und Sie Ihren Namen dann verbessern - wie list oder temp wirklich nicht den Leser sprechen, was die Verwendungen beabsichtigen diese Variablen sind.

Answer 2

list.add(temp) wird Verweis auf das gleiche Objekt temp der Liste hinzufügen. Später entfernen Sie Elemente daraus, bis sie leer sind, und der Algorithmus endet mit einer Liste, die mehrere Referenzen auf dieselbe leere Liste enthält.

Mit new ArrayList(temp) (oder noch besser - der typsichere new ArrayList<>(temp)) wird eine neue Liste mit dem gleichen Inhalt wie temp erstellen, so später, wenn Sie Elemente aus temp entfernen, wird diese Liste nicht betroffen.