Когда использовать 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. Я пытался, но получаю ошибки. Если у кого-то есть предложения, пожалуйста, дайте мне знать. Основная цель задать этот вопрос состоит в том, что я хочу знать, когда я предпочитаю ArrayLists над массивами в задачах рекурсии.

P.S. Прошу прощения за плохой отступ, так как мне пришлось печатать всю программу из-за ограничений серфинга, а также из-за некоторых синтаксических ошибок, но я старался изо всех сил. Спасибо Мохит

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 - это изменяемый тип String, который позволяет легко добавлять и удалять символы. Это было бы отличным решением и для этой проблемы:

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);
        }
    }
}

Answer 2

Вы хотите избежать передачи больших структур данных по значению во время рекурсии, поскольку они могут занимать много памяти. Это единственное, о чем я могу думать, в общем. Передача ссылки на массив или ArrayList - это нормально. Я предпочитаю ArrayList в целом.

Посмотрите на Java Stack класс для этой проблемы, в частности.

Answer 3

Я понял, что никто (включая меня) на самом деле не ответил на ваш вопрос.Я думаю, что вы были убеждены, что использование ArrayList здесь нежелательно.Но как вы могли бы заставить его работать?

Самый простой способ - подделать с ним стек:

public static void printSol(int cn, int on, ArrayList<Character> sol) {
   //...
   sol.add('(');
   printSol(on - 1, cn, sol);
   sol.remove(sol.size() - 1);