Есть ли способ написать это, используя массив строк вместо массива? - PullRequest
Новая
       39

Есть ли способ написать это, используя массив строк вместо массива?

0 голосов
/ 11 апреля 2019

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

public static ArrayList<String> combinations(String nChars, int k) 
    {
        int n = nChars.length();
        ArrayList<String> combos = new ArrayList<String>();
        if (k == 0) 
        {
            combos.add("");
            return combos;
        }
        if (n < k || n == 0)
            return combos;
        String last = nChars.substring(n-1);
        combos.addAll(combinations(nChars.substring(0, n-1), k));
        for (String subCombo : combinations(nChars.substring(0, n-1), k-1)) 
            combos.add(subCombo + last);

        return combos;
    }

    public static void main(String[] args) 
    {
        String nChars = "ABCDEF";
        System.out.println(combinations(nChars, 4));
    }

Ответы [ 2 ]

3 голосов
/ 11 апреля 2019

Предоставленный код использует ArrayList поверх классического String [] (массив строк), поскольку ArrayLists имеют динамический размер, а также удобные методы для добавления, изменения и удаления элементов, не беспокоясь о превышении размера массива.Если вы хотите узнать больше, вот документация Java для ArrayLists .

Причина, по которой вы получаете ошибку при замене ArrayList на ванильный массив, заключается в том, что сам массив имеетни один из методов (например, combos.add(subCombo + last);), которые определены ArrayList.Если вы хотите заменить ArrayList на массив, вам придется выполнить соответствующие действия вручную.

РЕДАКТИРОВАТЬ: Я идиот и не читал заголовок вопроса.Хотя технически было бы возможно переписать это с использованием массива String, нам потребовалось бы знать, сколько возможных комбинаций мы могли бы добавить в наш массив combos, чтобы мы могли выделить соответствующее количество места (то есть String[] combos = new String[num]).Вычисление num будет либо утомительным, либо выделит слишком много места для массива, израсходовав ненужные объемы памяти.Лучше всего оставить управление памятью ArrayList и большую часть времени беспокоиться о текущей проблеме.

0 голосов
/ 11 апреля 2019

combos.addAll (комбинации (nChars.substring (0, n-1), k));

Этот вызов показывает основное различие между массивами и реализациями интерфейса List

  • во-первых, вы можете вызывать методы из списка
  • во-вторых, вам не нужно беспокоиться о размере этой структуры данных

Другими словами: чтобы переписать ваш код для использования чистого массива, вам нужно отслеживать текущий размер массива и при добавлении новых записейВы должны увеличить размер вашего массива.Делая все то, что ArrayList неявно делает для вас: выделение нового массива, копирование всех старых записей, чтобы затем, наконец, вставить новые, которые вы намереваетесь добавить.

...