中国建设信息化官网,无锡网站搜索引擎优化,视频 播放网站怎么做,阿里云网站建设需要多少钱LeetCode T491 递增子序列 题目链接:491. 递增子序列 - 力扣#xff08;LeetCode#xff09;
题目思路: 首先这里的测试用例很容易误导我们,这道题不能使用上次子集的思路对数组先排序,使用一个used数组来解决问题. 我们用[4,7,6,7]举例这道题的递增序列不存在[4,6,7,7]这个…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是每一层都会重置的,无需回溯,每一层回溯会自动置空 SetInteger set new HashSet();//每一层用来记录,去重for(int i startIndex;inums.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,i1);path.remove(path.size()-1);} 题目代码:
class Solution {ListInteger path new ArrayList();ListListInteger result new ArrayList();public ListListInteger findSubsequences(int[] nums) {backtracking(nums,0);return result;}public void backtracking(int[] nums,int startIndex){if(path.size()2){result.add(new ArrayList(path));}SetInteger set new HashSet();for(int i startIndex;inums.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,i1);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;inums.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 {ListInteger path new ArrayList();ListListInteger result new ArrayList();boolean[] used;public ListListInteger 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;inums.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(i0 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;inums.length;i){if(i0 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 {ListInteger path new ArrayList();ListListInteger result new ArrayList();boolean used[];public ListListInteger 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;inums.length;i){if(i0 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;//回溯}}}
}
