代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II
1.题目
1.1递增子序列
-
文档讲解:https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html
-
解题思路:回溯
-
用[4, 7, 6, 7]这个数组来举例,抽象为树形结构如图:
-
-
代码:
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { backtracking(nums, 0); return result; } void backtracking(int[] nums, int startIndex) { if(path.size() >= 2){ result.add(new ArrayList<>(path)); } Set<Integer> tempSet = new HashSet<>();// 使用set对本层元素进行去重 for (int i = startIndex; i < nums.length; i++) { if((!path.isEmpty() && nums[i] < path.get(path.size() - 1)) || tempSet.contains(nums[i])){ continue; } tempSet.add(nums[i]); path.add(nums[i]); backtracking(nums,i + 1); path.remove(path.size() - 1); } } }
-
总结:
- 本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑!
- 数组,set,map都可以做哈希表,而且数组干的活,map和set都能干,但如果数值范围小的话能用数组尽量用数组。
1.2全排列
-
视频讲解:组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili
-
文档讲解:https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html
-
解题思路:回溯
-
以[1,2,3]为例,抽象成树形结构如下:
-
回溯三部曲
-
递归函数参数
List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); void backtracking(int[] nums,boolean[] used)
-
递归终止条件
if(path.size() == nums.length){ result.add(new ArrayList<>(path)); return; }
-
单层搜索的逻辑
for(int i = 0;i < nums.length;i++){ if(used[i] == true){ continue; } path.add(nums[i]); used[i] = true; backtracking(nums,used); used[i] = false; path.remove(path.size() - 1); }
-
-
-
代码:
class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> path = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] used = new boolean[nums.length]; backtracking(nums,used); return result; } void backtracking(int[] nums,boolean[] used){ if(path.size() == nums.length){ result.add(new ArrayList<>(path)); return; } for(int i = 0;i < nums.length;i++){ if(used[i] == true){ continue; } path.add(nums[i]); used[i] = true; backtracking(nums,used); used[i] = false; path.remove(path.size() - 1); } } }
-
总结:
- 每层都是从0开始搜索而不是startIndex
- 需要used数组记录path里都放了哪些元素了
1.3全排列 II
-
文档讲解:https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html
-
解题思路:回溯
-
去重一定要对元素进行排序,这样我们才方便通过相邻的节点来判断是否重复使用了。
-
以示例中的 [1,1,2]为例 (为了方便举例,已经排序)抽象为一棵树,去重过程如图:
-
图中我们对同一树层,前一位(也就是nums[i-1])如果使用过,那么就进行去重。
-
-
代码:
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.sort(nums); backtracking(nums, used); return result; } void backtracking(int[] nums, boolean[] used) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } if (used[i] == true) { continue; } path.add(nums[i]); used[i] = true; backtracking(nums, used); used[i] = false; path.remove(path.size() - 1); } } }
-
总结:
- 一般来说:组合问题和排列问题是在树形结构的叶子节点上收集结果,而子集问题就是取树上所有节点的结果。