我一直在练习算法,递归总是我的弱点。这个问题要求将嵌套数组压缩为一个单一的数组。如果使用循环给出一个O(n^3) [给定相同大小的3d数组]的解决方案将会很简单。
然而,我已经在苦斗几个小时了。这就是我目前拥有的,请注意,我尝试了不同的解决方案,这只是我决定留给大家发布的。
我想要两件事情,第一,是否有办法修复我的当前代码以获得正确的输出;第二,是否有更简单和更清晰的用递归编写此代码的方式,谢谢!
额外问题:如果我不知道嵌套数组的维数,我该如何使用递归解决此问题?
编辑 好吧,在一些硬编码之后(我不想这样做),我设法使这个问题得到解决。但代码现在是硬编码且非常混乱,是否有办法清理代码或使用更简单的方法使用递归解决此问题?
编辑2 我正在尝试使用辅助方法递归重新做这个问题。我会看看是否可以使用这种风格更好地解决问题。
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 使用递归帮助后,我几乎有了答案,但最后一个元素不会添加到ArrayList中。
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