Java-使用递归展平数组 [英] Java- Flatten an array using recursion
问题描述
我一直在练习算法，而递归始终是我的弱点.此问题要求将嵌套数组展平为单个数组.如果使用给出O(n ^ 3)[给定大小相等的3d数组]解决方案的循环，这将很简单.
I have been practicing algorithms, and recursion is always my weak point. This problem asks to flatten a nested array into a single array. This would be simple if using a loop giving an O(n^3) [given an equally sized 3d array] solution.
但是对于递归来说，我已经挣扎了几个小时.这就是我所拥有的，请注意，我已经花了很多时间尝试各种解决方案的代码，这就是我决定将其发布给大家的原因.
However with recursion I have been struggling for a few hours. This is what I have, please note I have dabbled with my code trying out different solutions, this is just what I decided to leave it at to post up to you guys.
我想要做的两件事，是否有任何方法可以修复当前代码以获取正确的输出，并且有一种更简单，更轻松的方式使用递归编写此代码的方法，谢谢！
What I want are two things, is there anyway to fix my current code to get the correct output, and is there a simpler and less messy way to write this code using recursion, thanks!
奖金问题，如果我不知道嵌套数组的维数，那么我如何使用递归来解决这个问题?
Bonus Questions, if I did not know the dimensions of the nested array, how would I go about this problem then using recursion?
EDIT 好了，经过一些硬编码(我不想这样做)之后，我设法使它开始工作.但是代码现在是硬编码的，而且非常混乱，是否有必要清理代码或采用更简单的方法来使用递归来解决此问题?
EDIT Ok so after some hard coding(which i do not want to do), I managed to get this to work. But the code is now hard coded and very messy, is there anyway to clean up the code or go about a simpler way to solve this using recursion?
EDIT2 我正在尝试使用辅助方法递归重做此问题.我看看使用这种样式是否能带来更好的运气
EDIT2 I am attempting redo-ing this problem using helper method recursion. I'll see if I have better luck using this style
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，
output: 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中.
Edit3 After using helper recursion I almost have the answer, but the last element wont add to the 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，
output: 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,
推荐答案
它是递归的，您不需要更改输入结构，也不需要知道数组的维数.您可以疯狂地混合使用Arrays，Lists和其他对象，它将返回一个ArrayList:
It's recursive, you don't need to change the input structure and it doesn't need to know the dimension of your array. You can go crazy and mix Arrays, Lists and other objects, it will return an 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]
Here's a modified version, which also flatten Maps to a collection of values. It can output either a Set or a List.
这是我最初的解决方案，仅显示结果，但返回void:
Here is my original solution, which only displayed the results, but returned void :
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，
It returns : 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,
这篇关于Java-使用递归展平数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
