Назначение объекта Java ArrayList
Я не понимаю строку "arr[c-'a']=new ArrayList();" в коде ниже. Без него код не работает.
Замена
List<Queue<Character>> list=arr[c-'a'];
arr[c-'a']=new ArrayList();
с
List<Queue<Character>> list=new ArrayList(arr[c-'a']);
может работать. Но это будет иметь проблемы с производительностью в большом наборе данных.
Что "arr[c-'a']=new ArrayList();" делает?
//Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.
package test.Test;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
class Test
{
int MatchingSubseq(String s, String[] words) {
List<Queue<Character>>[] arr=new ArrayList[26];
for(int i=0; i<26; i++)
arr[i]=new ArrayList<>();
for(String w:words){
Queue<Character> que=new ArrayDeque<>();
for(var c:w.toCharArray()){
que.add(c);
}
arr[que.peek()-'a'].add(que);
}
int res=0;
for(char c:s.toCharArray()){
List<Queue<Character>> list=arr[c-'a'];
arr[c-'a']=new ArrayList();
for(Queue<Character> q:list){
q.poll();
//System.out.println(q);
if (q.size()==0)
res++;
else
arr[q.peek()-'a'].add(q);
}
}
return res;
}
// Driver Program
public static void main(String[] args)
{
String s = "abcde";
String[] words = {"a","bb","acd","ace"};
Test test=new Test();
System.out.println(test.MatchingSubseq(s, words));
}
}
Редактировать:
если закомментировать "arr[c-'a']=new ArrayList();", я увижу ошибку, как показано ниже. Это происходит только в некоторых онлайн-компиляторах. Странный...
Редактировать: обновил код и набор входных данных, чтобы увидеть ошибку.
Ответы 4
Вопрос в том, что делает приведенный ниже код:
arr[c-'a'] = new ArrayList();
Он присваивает новый ArrayList по индексу c - 97 в массиве arr, где 97 является int значением char со значением 'a'.
Эта логика используется для доступа к массиву с использованием значений a-z путем преобразования их в индексы 0-25, используя тот факт, что char неявно является числовым типом данных (16-битное целое число без знака) в Java.
Другой способ задать этот вопрос заключается в том, чем отличается List<Queue<Character>> list=arr[c-'a']; arr[c-'a']=новый ArrayList(); и List<Queue<Character>> list=new ArrayList(arr[c-'a']);
Второй создает копию списка, первый создает пустой список. Для большого списка копирование серьезно повлияет на производительность.
У вас есть массив с 26 элементами, пронумерованными от 0 до 25.
Но вы используете этот массив для хранения информации для каждого символа от 'a' до 'z'. Итак, для каждого символа вам нужно преобразовать букву ('a'-'z') в число от 0 до 25, чтобы иметь возможность найти его в массиве.
Самый простой способ преобразовать 'a' в 0, 'b' в 1 и так далее, вплоть до преобразования 'z' в 25, — вычесть значение 'a'. Это работает, потому что 'a' на самом деле имеет числовое значение, но вам не нужно знать это значение, чтобы написать код, в котором 'a' вычитается.
В вашем коде c — это переменная char, c - 'a' вычисляет разницу между значением char в переменной c и 'a'.
Таким образом, с помощью arr[c-'a'] вы назначаете запись в этом c - 'a' индексе массива.
"arr[c-'a']=новый ArrayList();" это как использовать новый ArrayList для замены старого. Если вы закомментируете его, старый ArrayList останется в arr[c-'a']. В некоторых случаях, например "bb", "arr[q.peek()-'a'].add(q);" добавит Queue в ArrayList, который зацикливается, и вызовет исключение ConcurrentModificationException.
"List<Queue> list=new ArrayList(arr[c-'a']);" это только создать копию старого ArrayList, поэтому он не вызовет исключение ConcurrentModificationException в цикле, а старую очередь, которую вы должны удалить, все еще в списке. Поэтому окончательный результат может быть больше, чем ваш, за исключением. Такие как
String s = "abbcde";
String[] words = {"a","bb","acd","ace", "bz"};
"arr[c-'a']=новый ArrayList();" вернет 4, но "List<Queue> list=new ArrayList(arr[c-'a']);" вернется 6
Это может быть то, что я ищу - в некоторых случаях, например, "bb", "arr[q.peek()-'a'].add(q);" добавит Queue в ArrayList, который зацикливается, и вызовет исключение ConcurrentModificationException.
Оба "arr[c-'a']=new ArrayList();" и "List<Queue> list=new ArrayList(arr[c-'a']);" вернет 3 правильно. Почему "List<Queue> list=new ArrayList(arr[c-'a']);" нет проблемы с циклом?
Потому что "List<Queue> list=new ArrayList(arr[c-'a']);" создаст новый ArrayList, цикл ниже будет проходить по новому ArrayList и добавлять Queue к старому ArrayList. Есть два ArrayList, вы используете расширенный цикл for для обхода нового ArrayList и добавления элемента в старый, это не вызовет ConcurrentModificationException.
Этот алгоритм требует удаления старого значения из обр. Если вы используете «List<Queue> list=new ArrayList(arr[c-'a']);», когда String s имеет один и тот же символ, он вернет большее значение, чем исходный код.
Я уже инициировал его в ``` for(int i=0; i<26; i++) arr[i]=new ArrayList<>();``` и вычислил arr[i]. Почему мне нужно инициировать там снова?