Java-使用遞歸展平數組

Question

我一直在練習算法，而遞歸總是我的弱點。此問題要求將嵌套數組平鋪爲單個數組。如果使用給定O（n^3）[給定相同大小的3d陣列]解決方案的循環，這將很簡單。

然而隨着遞歸，我一直在掙扎幾個小時。這是我的，請注意我已經涉足了我的代碼嘗試不同的解決方案，這正是我決定留下來發布給你們。

我想什麼是兩件事情，反正是有解決我當前的代碼，以獲得正確的輸出，並且是有使用遞歸，感謝寫這個代碼更簡單，更混亂的方式！

獎金問題，如果我不知道嵌套陣列的尺寸，我將如何去了解這個問題，然後使用遞歸？

編輯 好了，所以經過一番硬編碼（我不想做），我設法得到這個工作。但是，代碼現在是硬編碼，非常混亂，有無論如何清理代碼或採用遞歸解決這個問題的簡單方法嗎？

EDIT2 我試圖重做-ING使用helper方法遞歸這個問題。我去看看，如果我使用這種風格有更好的運氣

import java.io. * ; 
    import java.util. * ; 
    class Solution { 
    // static int oneLen = 0; 
    //static int twoLen = 0; 
    //static int threeLen = 0; 

    static int oneCnt = 0; 
      static int twoCnt = 0; 
      static int threeCnt = 0; 
      static ArrayList <Integer> result = new ArrayList <Integer>(); 
      public static ArrayList <Integer> flatten(int [][][] arr){ 

    if (oneCnt < arr[threeCnt][twoCnt].length && !(oneCnt == 2 && twoCnt == 2 && threeCnt == 2)) 
    { 


    if (oneCnt == 0 && twoCnt == 0 && threeCnt == 0){ 
    result.add(arr[threeCnt][twoCnt][oneCnt]); 
      oneCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line One"); 
      System.out.println("Count1: " + oneCnt); 
      System.out.println("Count2: " + twoCnt); 
      System.out.println("Count3: " + threeCnt); 
    } 
    oneCnt++; 
      if (oneCnt != 3){ 
    result.add(arr[threeCnt][twoCnt][oneCnt]); } 






    System.out.println("Line One"); 
      System.out.println("Count1: " + oneCnt); 
      System.out.println("Count2: " + twoCnt); 
      System.out.println("Count3: " + threeCnt); 
      flatten(arr); 
    }  else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt < arr[threeCnt].length - 1){ 


    //oneLen = 0;  
    oneCnt = 0; 
      // twoLen++; 


      twoCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneCnt); 
      System.out.println("Count:2 " + twoCnt); 
      System.out.println("Count:3 " + threeCnt); 
      flatten(arr); 
    } 

    else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt == arr[threeCnt].length - 1 && threeCnt < arr.length - 1){ 

    oneCnt = 0; 
    twoCnt = 0; 
      threeCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line Three"); 
      System.out.println("Count:1 " + oneCnt); 
      System.out.println("Count:2 " + twoCnt); 
      System.out.println("Count:3 " + threeCnt); 
      flatten(arr); 
    } 
    return result; 
    } 
    public static void main(String[] args) { 
    int[][][] array = 
    { { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} }, 
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} }, 
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } }; 
      flatten(array); 
      for (int i = 0; i < result.size(); i++){ 
    System.out.print(result.get(i) + ","); 
    } 
    } 
    } 

輸出：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ，16,17,18,19,20,21,22,23,24,25,26,27，

EDIT3 使用的輔助遞歸我幾乎有答案，但最後一個元素後不會添加到數組列表。

import java.io. * ; 
    import java.util. * ; 
    class Solution { 



    static ArrayList <Integer> result = new ArrayList <Integer>(); 
      public static void flatten(int [][][] arr){ 
    int oneLen = 0; 
      int twoLen = 0; 
      int threeLen = 0; 
      flattenHelper(arr, oneLen, twoLen, threeLen); 
    } 

    public static void flattenHelper(int [][][] arr, int oneLen, int twoLen, int threeLen){ 

    if (oneLen < arr[threeLen][twoLen].length - 1){ 
    System.out.println("Line One"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen + 1, twoLen, threeLen); 
    } 
    else if (twoLen < arr[threeLen].length - 1){ 
    System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen = 0, twoLen + 1, threeLen); 
    }  else if (threeLen < arr.length - 1){ 
    System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen = 0, twoLen = 0, threeLen + 1); 
    } 

    } 

    public static void main(String[] args) { 
    int[][][] array = 
    { { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} }, 
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} }, 
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } }; 
      flatten(array); 
      for (int i = 0; i < result.size(); i++){ 
    System.out.print(result.get(i) + ","); 
    } 
    } 
    } 

輸出：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21 ，22,23,24,25,26，

Answer 1

它是遞歸的，你不需要改變輸入結構，也不需要知道數組的維數。你可以去瘋狂和混合陣列，列表和其他物體，它會返回一個ArrayList：

package stackOverflow; 

import java.lang.reflect.Array; 
import java.util.ArrayList; 
import java.util.List; 

public class Solution 
{ 
    public static void main(String[] args) { 
     int[][][] int3dArray = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, 
       { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } }, 
       { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 }, { 29, 30 } } }; 
     String[][] string2dArray = { { "He, llo" }, { "Wo", "rld" } }; 
     String[] stringArray = { "Hello", "World" }; 
     Object[] objectArray = { "Hell", 0, "W", 0, "rld" }; 

     List<Object> mixList = new ArrayList<Object>(); 
     mixList.add("String"); 
     mixList.add(3); 
     mixList.add(string2dArray); 

     System.out.println(flatten(int3dArray)); 
     System.out.println(flatten(flatten(int3dArray))); 
     System.out.println(flatten(3)); 
     System.out.println(flatten(stringArray)); 
     System.out.println(flatten(string2dArray)); 
     System.out.println(flatten(objectArray)); 
     System.out.println(flatten(mixList)); 
    } 

    private static List<Object> flatten(Object object) { 
     List<Object> l = new ArrayList<Object>(); 
     if (object.getClass().isArray()) { 
      for (int i = 0; i < Array.getLength(object); i++) { 
       l.addAll(flatten(Array.get(object, i))); 
      } 
     } else if (object instanceof List) { 
      for (Object element : (List<?>) object) { 
       l.addAll(flatten(element)); 
      } 
     } else { 
      l.add(object); 
     } 
     return l; 
    } 
} 

它輸出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] 
[3] 
[Hello, World] 
[He, llo, Wo, rld] 
[Hell, 0, W, 0, rld] 
[String, 3, He, llo, Wo, rld] 

這裏有一個modified version，這也扁平化映射到值的集合。它可以輸出Set或List。

這是我原來的解決方案，其中僅顯示的結果，但返回無效：

package stackOverflow; 

import java.lang.reflect.Array; 


public class Solution 
{ 
    public static void main(String[] args) { 
     int[][][] array = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, 
       { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } }, 
       { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 } } }; 
     flatten(array); 
    } 

    private static void flatten(Object object) { 
     if (object.getClass().isArray()) { 
      for (int i = 0; i < Array.getLength(object); i++) { 
       flatten(Array.get(object, i)); 
      } 
     } else { 
      System.out.print(object + ","); 
     } 
    } 
} 

它返回： 1,2,3,4,5,6,7,8,9,10 ，11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28，

Answer 2

如果你可以改變數據是整數，而不是爲int數組，你可以檢查傳入數組的元素和遞歸對於那些數組中的元素，或只是將它們添加如果不是，則直接返回結果。

public static ArrayList<Integer> flatten(Object [] arr) { 
    ArrayList<Integer> result = new ArrayList<>(); 

    for (int i = 0; i < arr.length; i++) { 
     if (arr[i].getClass().isArray()){ 
      result.addAll(flatten((Object[])arr[i])); 
     } else { 
      result.add((int)arr[i]); 
     } 
    } 

    return result; 
}