java - 何时在递归中使用 ArrayList 而不是数组

Question

所以我有这个问题。我试图编写一个程序来打印所有有效的可能的括号排列，即对于 3 个括号，我们可以有 ((()))、(()())、()()()、(())()等等

我有一个工作代码

public static void main(String[] args) {
    int number = 3; // No. of brackets
    int cn = number;
    int on = number;
    // open and closed brackets respectively
    char[] sol = new char[6];
    printSol(on, cn, sol, 0);
}

public static void printSol(int cn, int on, char[] sol, int k) {
    if (on == 0 && cn == 0) {
        System.out.println("");
        for (int i = 0; i < 6; i++) {
            System.out.print(sol[i]);
        }
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol[k] = '(';
                printSol(on - 1, cn, sol, k + 1);
            }
        }

        if (cn > on) {
            sol[k] = ')';
            printSol(on, cn - 1, sol, k + 1);
        }
    }
}

现在的问题是我想使用 ArrayList 而不是使用 char 数组来执行此操作。 我尝试过，但出现错误。如果有人有任何建议，请告诉我。问这个问题的主要目的是我想知道在递归问题中什么时候我应该更喜欢ArrayList而不是数组。

附注 对于糟糕的缩进，我感到很抱歉，因为由于冲浪限制，我不得不输入整个程序，而且可能存在一些语法错误，但我尽力了。 谢谢 莫希特

Answer 1

我认为你使用 char[] 做得很好。速度很快，而且切中要点。

我想说你在实践中遇到的大多数递归问题都不遵循这种模式。这是因为，通常，对于需要递归的问题，您会在搜索树上执行搜索以实现一个特定目标(树上的一个特定叶节点)。您正在执行迭代:您正在尝试访问树上的每个叶节点，并为每个叶节点执行一个操作。

使用常见的搜索算法(例如深度优先搜索)，您不需要在递归时准备结果，而是在找到目标后放松时准备结果。

但是对于您这样做的情况，char[]效果很好。您基本上是通过参数 sol 来模拟堆栈。和k (sol 保存数据，而 k 指向栈顶)。正如其他人所注意到的，您可以直接使用堆栈(通过传递 Deque<Character> 实现，通常是 LinkedList )。

在我心中ArrayList是一种倒退。如果您要使用集合，请使用针对该问题制作的集合。

编辑:这是一个未经测试的使用 Deque 的实现:

public static void printSol(int cn, int on, Deque<Character> sol) {
    if (on == 0 && cn == 0) {
        System.out.println("");
        for ( Iterator<Character> it = sol.descendingIterator(); it.hasNext(); ) {
            System.out.println(it.next());
        }
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol.push('(');
                printSol(on - 1, cn, sol);
                sol.pop();
            }
        }

        if (cn > on) {
            sol.push(')');
            printSol(on, cn - 1, sol);
            sol.pop();
        }
    }
}

//...
printSol(3, 3, new ArrayDeque<Character>(6));

如您所见，变化很少。

编辑 2: 对于这个具体问题，我们根本没有讨论过的一件事是 StringBuilder .

StringBuilder 是一种可变的字符串类型，可让您轻松添加和删除字符。这也是解决这个问题的一个很好的解决方案:

public static void printSol(int cn, int on, StringBuilder sol) {
    if (on == 0 && cn == 0) {
        System.out.println(sol);
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol.append('(');
                printSol(on - 1, cn, sol);
                sol.deleteCharAt(sol.length()-1);
            }
        }

        if (cn > on) {
            sol.append(')');
            printSol(on, cn - 1, sol);
            sol.deleteCharAt(sol.length()-1);
        }
    }
}