代码随想录Day24 LeetCode T491 递增子序列 LeetCode T46 全排列 LrrtCode T47 全排列II

LeetCode T491 递增子序列

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

题目思路:

首先这里的测试用例很容易误导我们,这道题不能使用上次子集的思路对数组先排序,使用一个used数组来解决问题.

我们用[4,7,6,7]举例这道题的递增序列不存在[4,6,7,7]这个子序列,而如果我们对数组先进行排序,就会得到错误答案.

这题的实质是让我们在数组中递增的取出元素,实际上是我们取出的元素是有序的,这里我们可以定义一个set来解决问题,实际上我们要做的仍然是树层去重,这里只要对每一层的元素进行一次去重即可

1.函数定义

其他的都定义为全局变量了,只需这两个参数即可

public void backtracking(int[] nums,int startIndex)

2.终止条件

这题跟之前一样,不需要终止条件,因为我们收集的是树的所有节点,而不是叶子结点,但是题目要求我们的path至少要大于等于2,所以我们就以这个为条件来收集结果.

        if(path.size()>=2){result.add(new ArrayList(path));}

3.一次搜索逻辑(for循环)

注:为什么set不需要回溯?

因为set是每一层都会重置的,无需回溯,每一层回溯会自动置空

 Set<Integer> set = new HashSet<>();//每一层用来记录,去重for(int i = startIndex;i<nums.length;i++){if( !path.isEmpty() && path.get(path.size()-1) > nums[i] || set.contains(nums[i])){continue;}set.add(nums[i]);path.add(nums[i]);backtracking(nums,i+1);path.remove(path.size()-1);}

题目代码:

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return result;}public void backtracking(int[] nums,int startIndex){if(path.size()>=2){result.add(new ArrayList(path));}Set<Integer> set = new HashSet<>();for(int i = startIndex;i<nums.length;i++){if( !path.isEmpty() && path.get(path.size()-1) > nums[i] || set.contains(nums[i])){continue;}set.add(nums[i]);path.add(nums[i]);backtracking(nums,i+1);path.remove(path.size()-1);}}
}

LeetCode T46 全排列

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

题目思路:

首先这题我们可以先画出树状图,这题的重点就是used数组的使用

因为排列是有序的,所以[1,2]和[2,1]是两个完全不同的排列,这里可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex,但是需要使用used数组,因为一个排列中nums数组中的每个元素都只能出现一次,这里我们就需要标记已经出现的元素,如果它还想出现,就可以直接continues这次循环即可,下面我们进行回溯三部曲

1.回溯函数参数

这里不需要根据startIndex来判断取值区间,也是和子集不同的地方,这里我们直接传入nums数组即可

    public void backtracking(int[] nums)

2.确定终止条件

这里是在叶子结点取值而不是取每个节点的值,所以需要终止条件,因为我们需要获得的是数组的排列,所以当path收集的元素长度到达数组的长度,即是一次有效的排列

        if(path.size() == nums.length){result.add(new ArrayList(path));return;}

3.一次搜索逻辑

这里我们首先不能再一次排列中重复出现某元素,所以在添加元素之前先判断该元素是否出现过,出现过那么该次全排列无效,则跳出本轮循环,下面就是经典的递归和回溯过程

        for(int i = 0;i<nums.length;i++){if(used[i]){continue;}path.add(nums[i]);used[i] = true;backtracking(nums);path.remove(path.size()-1);used[i] = false;}

题目代码:

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];backtracking(nums);return result;}public void backtracking(int[] nums){if(path.size() == nums.length){result.add(new ArrayList(path));return;}for(int i = 0;i<nums.length;i++){if(used[i]){continue;}path.add(nums[i]);used[i] = true;backtracking(nums);path.remove(path.size()-1);used[i] = false;}}
}

LeetCode T47 全排列II

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

题目思路:

这题的思路和上一题类似,由于本题可能存在重复元素,所以比上一题多了一个去重的逻辑,这题的去重逻辑和之前组合的逻辑是一样的,我们只需要先将数组排序,让相同的元素排在一起,使用一个used数组来标记已经使用过的元素,这里我们还是先画出树状图来帮助理解

我们发现相邻元素如果是相等的,那么相同元素中的第二个元素开始的路径就重复了,也就是我们说的树层去重,下面我摆出树层去重的逻辑

if(i>0 && nums[i] == nums[i-1] && !used[i-1])

其余代码和上面一样,我们依然按照回溯三部曲来操作

1.函数参数

由于其他元素都定义为全局变量了,所以直接使用一个nums即可,本题不需要startIndex来帮助我们规定选择元素的区间

public void backtracking(int[] nums)

2.终止条件

这题终止条件仍然是path收集的长度到达nums的长度即可

        if(path.size() == nums.length){result.add(new ArrayList(path));}

3.一次搜索逻辑

这里就涉及我们的去重逻辑了,下面由于没有startIndex约束,所以我们对选取的元素增加一个条件,就是选取的元素必须没有被使用过

 for(int i = 0;i<nums.length;i++){if(i>0 && nums[i] == nums[i-1] && !used[i-1]){continue;}if (!used[i]) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用path.add(nums[i]);backtracking(nums);path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复used[i] = false;//回溯}}

 

题目代码:

class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();boolean used[];public List<List<Integer>> permuteUnique(int[] nums) {used = new boolean[nums.length];Arrays.sort(nums);backtracking(nums);return result;}public void backtracking(int[] nums){if(path.size() == nums.length){result.add(new ArrayList(path));}for(int i = 0;i<nums.length;i++){if(i>0 && nums[i] == nums[i-1] && !used[i-1]){continue;}if (!used[i]) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用path.add(nums[i]);backtracking(nums);path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复used[i] = false;//回溯}}}
}