Ставь лайк, смотри, хорошая привычка! эта статьяGitHub GitHub.com/OU Ян SI H AI…Это было включено, это резюме Java-интервью с производителями первого уровня, на подведение итогов которого я потратил 3 месяца, и я принял предложение от крупной фабрики. Кроме того, оригинал статьи был впервые опубликован в моем личном блоге:blog.ouyangsihai.cn, Добро пожаловать в гости.
Эта статья объяснит, как сделать тему алгоритма возврата leetcode.За этот период времени я просмотрел все темы алгоритма возврата leetcode и нашел некоторые правила.Поэтому я хочу написать статью, чтобы подвести итог, Боюсь забыть позже.
Изучив тему алгоритма поиска с возвратом, я обнаружил, что его можно разделить на три категории: проблема подмножества, проблема комбинации и проблема перестановки. Что означают эти три категории? Позвольте мне привести пример, чтобы проиллюстрировать каждую.
проблема подмножестваскажем, массив[1,2,3], то соответствующая проблема подмножества состоит в том, что подмножество этого массива имеет:[],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3], это подмножество этого массива.Таких задач на leetcode много, и элементы в некоторых массивах задач могут повторяться, и тогда приходить к задаче подмножества.
комбинаторная задачаскажем, массив[1,2,3], комбинируя возможные варианты с целью 3, то есть:[1,2],[3], это проблема композиции в leetcode.
проблема перестановки, проблема перестановки относительно проста.Например, наша общая проблема полной перестановки, leetcode также имеет этот тип проблемы.
В этой статье мы поговорим о том, как использовать алгоритм возврата для решения этих задач.
1 Пошаговое объяснение структуры алгоритма поиска с возвратом
В начале я все же хочу использовать простой пример, чтобы показать вам шаг за шагом, как следует шаг за шагом решать проблему алгоритма поиска с возвратом. Алгоритм поиска с возвратом Framework; сначала посмотрите на следующую тему, которая является подмножеством темы, и сложность темы средняя.
Эта тема, рамки, заданные темой, таковы.
public List<List<Integer>> subsets(int[] nums) {
}
Итак, мы знаем, что сначала строимList<List<Integer>>Тип возвращаемого значения.
List<List<Integer>> list = new ArrayList<>();
Далее мы начинаем писать метод поиска с возвратом.
public void backTrace(int start, int[] nums, List<Integer> temp){
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Во-первых, это может быть написано так, как показано выше, передавая массивnums,startиtemp集合Он используется для сохранения результата.Затем каждый раз при обходе массива nums добавляется текущий элемент, а когда рекурсия возвращается, она откатывает и удаляет только что добавленный элемент.Разве не в этом идея отката .
Таким образом, базовая структура написана, и есть еще один вопрос, который необходимо рассмотреть.base case, тогда каков базовый случай для этой темы? На самом деле, поскольку это подмножество, каждый шаг необходимо добавлять к временному набору результатов, поэтому ограничений нет.
public void backTrace(int start, int[] nums, List<Integer> temp){
//每次都保存结果
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Наконец, давайте завершим это снова, и полный код будет готов.
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int j = 0; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
ок, запустим и посмотрим, как пойдет.
Он сказал, что я превысил ограничение по времени, указывая на то, что есть проблема с алгоритмом. Давайте посмотрим на код, который мы написали выше. Мы обнаружили, что на самом деле каждый раз, когда мы обходим массив, мы обходим с 0, что приводит к множеству повторяющихся пройденных элементов. , то есть мы должныstartПеременная не используется, наконец, мы начинаем обход каждый раз не с 0, а с текущего начала.Выбранные элементы мы исключаем, посмотрите на результаты.
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//从start开始遍历，避免重复
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Нашел идеальный проход, молодец! !
Кроме того, следует обратить внимание на один момент:list.add(new ArrayList<>(temp)); не пишите какlist.add(temp);, в противном случае выходным результатом будет пустой набор, и вы должны понять, почему, подумав об этом.
Проходите, эта тема, по сути, мы можем разобраться в общих рамках алгоритма возврата, а потом в будущем заняться другими темами, проследить за котом и нарисовать тигра, и просто сделать одну операцию.
назадbackTraceфункция на самом деле являетсявыбрать/отменить выборпроцесс, цикл for также является процессом выбора, и еще один момент заключается в том, что в этой функции необходимо обработать базовый случай. Затем мы можем разобраться с кадром.
public void backTrace(int start, int[] nums, List<Integer> temp){
base case处理
//选择过程
for(循环选择){
选择
backTrace(递归);
撤销选择
}
}
хорошо, я уже говорил о проблеме подмножества, теперь я придумаю более интересную тему подмножества.
2 проблемы с подмножеством
Тема, используемая для введения в структуру алгоритма поиска с возвратом, на самом деле относительно проста, но идея не изменилась, эта структура очень важна, а другие темы в основном изменены в вышеупомянутой структуре, например, операции сокращения.
90. Подмножество II средней сложности
По сравнению с предыдущими вопросами подмножества отличие состоит в том, что дополнение содержит повторяющиеся подмножества, то есть порядок нельзя изменить, и появляются подмножества с одинаковыми элементами.
Структура этой темы остается прежней, но необходимо выполнить простую операцию обрезки:Как исключить повторяющиеся подмножества.
Есть два пути решения этой проблемы, позже появляются и другие проблемы.нет повторяющихся подмножествЭти два метода могут быть использованы для решения таких ограничений.
- Способ 1. Используйте функцию «Установить дедупликацию» для решения проблемы.
Мы по-прежнему сначала удаляем указанный выше фреймворк, а затем модифицируем его.
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0){
return null;
}
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
//从start开始遍历，避免重复
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Поскольку мы хотим использовать характеристики Set для дедупликации, нам нужно добавить эту переменнуюSet<List<Integer>> set = new HashSet<>();, кроме того, в целях обеспечения порядка мы повторно сортируемArrays.sort(nums), что позволяет избежать проблемы повторяющихся подмножеств с одинаковыми элементами, но в другом порядке.
Итак, результат налицо.
List<List<Integer>> list = new ArrayList<>();
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
//排序
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
//set去重操作
if(!set.contains(temp)){
set.add(new ArrayList<>(temp));
list.add(new ArrayList<>(temp));
}
for(int j = start; j < nums.length; j++){
temp.add(nums[j]);
backTrace(j+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Посмотрите на результаты и обнаружите, что эффективность не очень хорошая.
Тогда давайте рассмотрим другую стратегию сокращения для дедупликации.
- Способ второй:
i > start && nums[i-1] == nums[i]
Почему эта стратегия обрезки возможна? Не волнуйтесь, позвольте мне нарисовать картинку, чтобы объяснить это.
Итак, мы можем сделать это таким образом.
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0){
return null;
}
Arrays.sort(nums);
List<Integer> temp = new ArrayList<>();
backTrace(0, nums, temp);
return list;
}
public void backTrace(int start, int[] nums, List<Integer> temp){
list.add(new ArrayList<>(temp));
for(int i = start; i < nums.length; i++){
//剪枝策略
if(i > start && nums[i] == nums[i-1]){
continue;
}
temp.add(nums[i]);
backTrace(i+1,nums,temp);
temp.remove(temp.size()-1);
}
}
Угу, вроде все в порядке.
3 комбинированные проблемы
Решив предыдущую проблему подмножества, вы обнаружите, что последняя проблема комбинации и проблема расположения не являются большой проблемой, они в основном представляют собой подпрограммы.
39. Комбинированная сумма средней сложности
Эта тема мало чем отличается от предыдущей, только нужно обратить внимание на один момент:Каждый номер может быть выбран в неограниченном количестве повторений, все, что нам нужно сделать, это когда рекурсивно,iне подписан изi+1начать, но сiНачинать.
backTrace(i,candidates,target-candidates[i], temp);
Давайте посмотрим на полный код.
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return list;
}
List<Integer> temp = new ArrayList<>();
backTrace(0,candidates,target,temp);
return list;
}
public void backTrace(int start, int[] candidates, int target, List<Integer> temp){
//递归的终止条件
if (target < 0) {
return;
}
if(target == 0){
list.add(new ArrayList<>(temp));
}
for(int i = start; i < candidates.length; i++){
temp.add(candidates[i]);
backTrace(i,candidates,target-candidates[i], temp);
temp.remove(temp.size()-1);
}
}
Это так просто! ! !
Итак, еще один комбинаторный вопрос.
40. Комбинированная сумма II, средняя сложность
Когда вы посмотрите на название, вы обнаружите, что оно почти такое же. Действительно, каждое число может быть использовано только один раз, и оно не может содержать повторяющихся комбинаций, поэтому используйте для его решения описанный выше метод дедупликации. Без лишних слов, давайте перейдем к коду.
List<List<Integer>> lists = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates.length == 0 || target < 0){
return lists;
}
Arrays.sort(candidates);
List<Integer> list = new LinkedList<>();
backTrace(candidates,target,list, 0);
return lists;
}
public void backTrace(int[] candidates, int target, List<Integer> list, int start){
if(target == 0){
lists.add(new ArrayList(list));
}
for(int i = start; i < candidates.length; i++){
if(target < 0){
break;
}
//剪枝：保证同一层中只有1个相同的元素，不同层可以有重复元素
if(i > start && candidates[i] == candidates[i-1]){
continue;
}
list.add(candidates[i]);
backTrace(candidates,target-candidates[i],list,i+1);
list.remove(list.size()-1);
}
}
Тоже идеальное решение! !
4 Проблема полной перестановки
Давайте начнем с самой простой задачи полной перестановки и быстро ее решим.
46. Все рейтинги средней сложности
Это полная компоновка, но порядок элементов другой, поэтому отсечение, которое нам нужно сделать, это исключить некоторые из временной коллекции.
код выше.
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0){
return lists;
}
List<Integer> list = new ArrayList<>();
backTrace(nums,list,0);
return lists;
}
public void backTrace(int[] nums, List<Integer> temp, int start){
if(temp.size() == nums.length){
lists.add(new ArrayList(temp));
return;
}
for(int i = 0; i < nums.length; i++){
//排除已有元素
if(temp.contains(nums[i])){
continue;
}
temp.add(nums[i]);
backTrace(nums,temp,i+1);
temp.remove(temp.size() - 1);
}
}
Разве это не скучно, организуйте это! !
47. Полный ранг II средней сложности
Хотя эта тема также полностью оформлена, она немного сложнее, чем предыдущая, с двумя оговорками:Есть повторяющиеся элементы, но не может содержать повторяющихся аранжировок.
Мы знаем, как решить неповторяющуюся полную расстановку, достаточно использовать предыдущий метод дедупликации, но как сделать так, чтобы наборы с одинаковыми элементами не имели повторяющихся расстановок?
Здесь нам нужноДобавьте массив посещений, чтобы записать, был ли посещен текущий элемент, так что проблема может быть решена.
public List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums.length == 0){
return result;
}
Arrays.sort(nums);
findUnique(nums,new boolean[nums.length],new LinkedList<Integer>());
return result;
}
public void findUnique(int[] nums, boolean[] visited,List<Integer> temp){
//结束条件
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return ;
}
//选择列表
for(int i = 0; i<nums.length; i++){
//已经选择过的不需要再放进去了
if(visited[i]) continue;
//去重
if(i>0 && nums[i] == nums[i-1] && visited[i-1]) break;
temp.add(nums[i]);
visited[i] = true;
findUnique(nums,visited,temp);
temp.remove(temp.size()-1);
visited[i] = false;
}
}
Это решает проблему.
5 это не резюме
На данный момент решены проблемы подмножества, комбинации и полной перестановки. От пошагового объяснения фреймворка до разбора конкретных проблем, все освещено, ха-ха, конечно, есть еще места, которые не посчитали вдумчивыми, надеюсь, вы мне что-нибудь посоветуете.
Эта статья писалась два дня, и она почти готова, быть оригинальным не просто, так что ставьте лайк!
Наконец, позвольте мне поделиться своим временемтри месяцав заключенииИнтервью по Java + Учебное пособие по технологии Java Backend, Это мой итог прошедших лет и весеннего набора. Я уже получил предложение от крупного производителя и оформил его в электронную книгу. Не буду благодарить вас за это. Каталог выглядит следующим образом:
Теперь поделитесь им со всеми бесплатно в моем общедоступном аккаунте нижеТехнический кружок программистаОтветитьинтервьюможет быть получен.