Korrekte Verwendung von Java-Liste Objekt

Question

Ich habe ein Programm geschrieben, um alle möglichen Teilmengen eines bestimmten Arrays zu berechnen.

class Solution { 
    /** 
    * @param S: A set of numbers. 
    * @return: A list of lists. All valid subsets. 
    */ 
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) { 
     // write your code here 
     if(nums == null) return null; 

     ArrayList<ArrayList<Integer>> res = new ArrayList<>(); 
     ArrayList<Integer> list = new ArrayList<>(); 

     helper(res, list, nums, 0); 

     return res; 
    } 

    private void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, int [] nums, int start) { 

     //res.add(list); 
     res.add(new ArrayList<Integer>(list)); 
     //System.out.println(list); 
     for(int i = start; i < nums.length; i++) { 
      list.add(nums[i]); 
      //System.out.println(list); 
      helper(res, list, nums, i+1); 
      list.remove(list.size()-1); 
     } 
    } 
} 

Das Programm funktioniert gut. Allerdings, wenn ich verwenden

res.add(list); 

statt

res.add(new ArrayList<Integer>(list)); 

Dann wird es das falsche Ergebnis. Zum Beispiel, wenn ich diesen Eingang gebe

int [] nums = new int[]{0}; 

Die erwartete Ausgabe ist [[], [0]]. Ich bekomme jedoch [[], []].

Fragen: 1.Weil ich versuche, das gleiche Objekt zu dem Objekt res hinzuzufügen. Ich nehme an, das res ArrayList-Objekt versucht zu überprüfen, ob das Listenobjekt bereits darin enthalten ist. Ist das richtig?

2.Warum bekomme ich [[], []]? Da das Listenobjekt in der Schleife auf [0] aktualisiert wird, warum wird es nicht zum res-Objekt hinzugefügt?

Answer 1

Sie erleben die Gefahren der Veränderlichkeit, und Sie haben eine gemeinsame Lösung gefunden: die defensive Kopie.

Wenn Sie das tun res.add(list), Sie setzen einen Referenz-list in res. Dann arbeiten Sie weiter mit der gleichen Liste und ändern sie. Da Sie mit dem gleichen Objekt arbeiten, wie Sie in res eingeben, wenn Sie es (hier mit remove()) ändern, dann drucken Sie es über res, Sie sehen die Änderungen an beiden Orten. Wenn Sie res.add(new ArrayList<Integer>(list)) machen, erstellt der Konstruktor ein neues Objekt ArrayList und kopiert alle Elemente von list hinein. Von nun an haben list und das neue Objekt keine Auswirkungen aufeinander. Wenn Sie list ändern, ändert sich Ihr neues Objekt nicht. Sie haben eine defensive Kopie gemacht.

Defensives Kopieren ist eine gut etablierte Methode, um mit diesem Problem umzugehen. Eine andere Möglichkeit, die viele Menschen für besser halten, besteht darin, die einmal erstellten Objekte nicht zu verändern. Lesen Sie etwas auf unveränderliche Objekte.

---

Bonus-Tipp: Code sieht sauberere und hat andere „gute“ Eigenschaften, wenn Sie die kürzeren Schnittstellennamen verwenden, anstatt die konkrete Art, wo immer möglich. Also:

public List<List<Integer>> subsets(int[] nums) ... 

List<List<Integer>> res = new ArrayList<>();