本文主要是介绍海智算法训练营第二十九天 | 第七章 回溯算法part05 | * 491.递增子序列* 46.全排列* 47.全排列 II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今日目标:
1.查找所有的非递减子序列
2.全排列
3.全排列II
1.查找所有的非递减子序列
题目:非递减子序列
原理:这道题不能用之前那种去重的方法,因为那些需要有序,这样只需要比较前后两个的值是否相同,而这道题不能使用排序,因为题目的要求是以当前序列的顺序找出他的非递减子序列。
例如:
- 输入: [4, 6, 7, 7]
- 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
所以,我们引用了set集合来充当uset数组来记录是否使用过这个数,也能达到理想的效果。
注意点:结束递归的出口是当path的长度大于等于二的时候,因为序列要求至少有两个数
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {dfs(nums,0);return res;}public void dfs(int[] nums , int start){if(path.size() >= 2) res.add(new ArrayList<>(path));if(start > nums.length -1) return;HashSet<Integer> hs = new HashSet<>();for (int i = start; i < nums.length; i++) {if(!path.isEmpty() && path.get(path.size()-1) > nums[i] || hs.contains(nums[i])){continue;}hs.add(nums[i]);path.add(nums[i]);dfs(nums,i+1);path.remove(path.size()-1);}}
}
2.全排列
题目:全排列
做法:这里我和题解不同的地方是我用的是hash集合来去重,感觉代码比较简单就没有看视频学习了。
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();HashSet<Integer> hs = new HashSet<>();public List<List<Integer>> permute(int[] nums) {dfs(nums);return res;}public void dfs(int[] nums){if(path.size() == nums.length){res.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if(hs.contains(nums[i])) continue;path.add(nums[i]);hs.add(nums[i]);dfs(nums);path.remove(path.size()-1);hs.remove(nums[i]);}
}
}
3.全排列II
题目:全排列II
class Solution {//存放结果List<List<Integer>> result = new ArrayList<>();//暂存结果List<Integer> path = new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] used = new boolean[nums.length];Arrays.fill(used, false);Arrays.sort(nums);backTrack(nums, used);return result;}private void backTrack(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// used[i - 1] == true,说明同⼀树⽀nums[i - 1]使⽤过// used[i - 1] == false,说明同⼀树层nums[i - 1]使⽤过// 如果同⼀树层nums[i - 1]使⽤过则直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] == false) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过,防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);//回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复used[i] = false;//回溯}}}
}
学习时长:3h
总结:更加熟悉了回溯的去重做法,以及了解了全排列的相关题目做法
这篇关于海智算法训练营第二十九天 | 第七章 回溯算法part05 | * 491.递增子序列* 46.全排列* 47.全排列 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!