4
Это вопрос: https://leetcode.com/problems/combinations/Java ArrayList клон улучшил время выполнения
Это мое решение 1:
public class Solution {
public List<List<Integer>> combine(int n, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();
combine(n, k, 1, result, new ArrayList<Integer>());
return result;
}
public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
if(k == 0){
result.add(l);
return;
}
for(int i = start; i <= n; ++i){
l.add(i);
combine(n, k - 1, i + 1, result, l);
}
}
}
Результат: небольшие тестовые случаи прошли. Но большие времена испытаний превышают.
Подача Результат: Лимит времени Превышен Последний выполнен вход: 10, 5
Решение 2:
public class Solution {
public List<List<Integer>> combine(int n, int k){
List<List<Integer>> result = new ArrayList<List<Integer>>();
combine(n, k, 1, result, new ArrayList<Integer>());
return result;
}
public void combine(int n, int k , int start, List<List<Integer>> result, ArrayList<Integer> l){
if(k == 0){
result.add(l);
return;
}
for(int i = start; i <= n; ++i){
ArrayList<Integer> a = (ArrayList<Integer>) l.clone();
a.add(i);
combine(n, k - 1, i + 1, result, a);
}
}
}
Сдал все тестовые случаи.
Главное отличие - это клон списка. Но почему? Решение является неправильным или просто медленным? Почему использование клона здесь быстрее? Действительно смущен.
Если вы не собираетесь изменять решения, вы можете сделать это лучше с общими связанными списками. –