回溯算法习题其二-Java【力扣】【算法学习day.16】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.非递增子序列

题目链接:491. 非递减子序列 - 力扣（LeetCode）

题面：

基本分析: 回溯暴力，可以维护一个set进行一些小剪枝

代码:

class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {dfs(nums, -1, new ArrayList<>());return res;}private void dfs(int[] nums, int idx, List<Integer> curList) {if (curList.size() > 1) {res.add(new ArrayList<>(curList));}Set<Integer> set = new HashSet<>();for (int i = idx + 1; i < nums.length; i++) {if (set.contains(nums[i])) { continue;}set.add(nums[i]);if (idx == -1 || nums[i] >= nums[idx]) {curList.add(nums[i]);dfs(nums, i, curList);curList.remove(curList.size() - 1);}}}
}

2.全排列

题目链接:46. 全排列 - 力扣（LeetCode）

题面:

基本分析:在上一题的基础上维护一个数组来记录元素是否被使用

代码:

class Solution {List<List<Integer>> list = new ArrayList<>();int len;public List<List<Integer>> permute(int[] nums) {len = nums.length-1;List<Integer> stack = new ArrayList<>();int[] arr = new int[len+1];recursion(nums,stack,arr);return list;}public void recursion(int[] nums,List<Integer> stack,int[] arr){if(stack.size()==len+1){list.add(new ArrayList<>(stack));}for(int i = 0;i<=len;i++){if(arr[i]==0){arr[i]=1;stack.add(nums[i]);recursion(nums,stack,arr);arr[i]=0;stack.remove(stack.size()-1);}}}
}

3.全排列II

题目链接:47. 全排列 II - 力扣（LeetCode）

题面:

基本分析:元素重复导致重复答案，利用set去重

代码:

class Solution {Set<List<Integer>> list = new HashSet<>();int len;public List<List<Integer>> permuteUnique(int[] nums) {len = nums.length-1;List<Integer> stack = new ArrayList<>();int[] arr = new int[len+1];recursion(nums,stack,arr);return new ArrayList<>(list);}public void recursion(int[] nums,List<Integer> stack,int[] arr){if(stack.size()==len+1){list.add(new ArrayList<>(stack));}for(int i = 0;i<=len;i++){if(arr[i]==0){arr[i]=1;stack.add(nums[i]);recursion(nums,stack,arr);arr[i]=0;stack.remove(stack.size()-1);}}}
}

4.重新安排行程

题目链接:332. 重新安排行程 - 力扣（LeetCode）

题面:

基本分析:对list排序和回溯暴力会超时最后一个样例，但是排序必不可少，参照下面这位的做法：

代码:

class Solution {List<String> ans = new ArrayList<>();Map<String, TreeMap<String, Integer>> map = new HashMap<>();public List<String> findItinerary(List<List<String>> tickets) {for (List<String> list : tickets) {String start = list.get(0);TreeMap<String, Integer> tmap = map.getOrDefault(start, new TreeMap<>());String end = list.get(1);int sum = tmap.getOrDefault(end, 0) + 1;tmap.put(end, sum);map.put(start, tmap);}ans.add("JFK");try {recursion(tickets.size() + 1);} catch (RuntimeException e) {}System.out.println(tickets.size());System.out.println(ans.size());return ans;}public void recursion(int n) {if (ans.size() == n)throw new RuntimeException();String start = ans.getLast();if(map.containsKey(start)){for (Map.Entry<String, Integer> entry : map.get(start).entrySet()) {int count = entry.getValue();if (count > 0) {ans.add(entry.getKey());entry.setValue(count - 1);recursion(n);entry.setValue(count);ans.removeLast();}}}}
}