回溯---递增子序列 Posted on 2021-07-27 00:00:00 2021-07-27 00:00:00 by Author 摘要 给定一个整型数组, 你能找到所有该数组的递增子序列吗???? # 递增子序列 1. 题目描述 - 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是 2 。 - **提示:** - 给定数组的长度不会超过15。 - 数组中的整数范围是 [-100,100]。 - 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。 2. 示例描述 - 示例一 - 输入:[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]] - 示例二 - 输入:[1,2,3] - 输出:[[1,2],[1,3],[2,3],[1,2,3]] 3. 解题思路 - 在拿到本题的时候,我发现这道题和之前回溯加递归的题一模一样,只要掌握掌握了递归与回溯算法,解决这道题就分分钟的事,但是写着写着发现自己还是太年轻了,这道题与之前的题还有点不太一样。不一样的地方在与递归寻找子序列过程中会出现重合的子集,在去重的这方面我卡住了,不知道怎么下手去重。 - 想了好久还是么想出来,于是就参考代码随想录Carl哥的题解,发现他的讲解思路真的太清楚了,解决我一直困扰的问题,就是在每一层递归时,怎么记住本次递归时使用的数尼,他巧妙的运用了数组来解决这个问题,每次递归遍历时就会开辟一个数组空间,记录本层已经使用的数,当下次再回到本层中时,如果本层之前的数与当前正在递归遍历的数相同的时候,说明这个数不需要递归了,如果递归,集合就会有重复的子集合,不满足题目结果。从而就这样解决了去重的问题。同时在每次遍历的时候开辟数组大小为多少合适尼,这就考虑到数组中绝对值最大的数是多少,我们就应该开辟最大数的2倍个存储空间个大小的数组(有负数存在,所以数组长度乘于二),所在题目提示中指出数组中元素取值都在-100到100之间,所以在每层开辟数组的时候,开辟一个大小为201的数组(-100到100一共有201个数,记得0也算啊),那么我们怎么记录使用过的数尼,因为数组下标不能为负数,所以数组中每个数平移100位,这就能保证数组中所有的元素在正数的范围内。我们就拿移动后的元素作为下标,这样如果该位置没有使用,那么在本次遍历的时候,本层的构造数组该位置置为一,等到下次遍历的本层的时候,如果该位置已经是一的话,说明本层之前的元素于正在遍历的元素相等,就跳过本元素的递归,就能达到去重的效果。这样就解决了我的问题。 - 具体实现逻辑如下,每一步都有具体的解释。 4. 代码示例 ```java //最终结果集 List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> findSubsequences(int[] nums) { //调用子集写的递归回溯算法,求得最后结果 trackBack(0,nums,new ArrayList<>()); return result; } public void trackBack(int index,int[]nums,List<Integer> temp){ //如果遍历过程中子集的长度大于等于2,那么该子集可以加入最终结果集 if(temp.size()>=2){ result.add(new ArrayList<>(temp)); } //每一层构造一个大小位201的数组,记录本层元素的使用情况,达到去重的效果 int[]used = new int[200]; //对于本层元素逐一进行递归操作 for (int i = index; i < nums.length; i++) { //如果临时集合不为空,并且集合最后一个元素大于当前遍历的元素 //或者当前元素在本层之前已经被使用了, // 那就跳过该元素的递归,继续寻找下一个符合要求的元素 if((!temp.isEmpty() && nums[i] < temp.get(temp.size()-1)) || used[nums[i]+100]==1) { continue; } //否则就把该元素置为已经使用过 used[nums[i]+100]=1; //并且把该元素加入零时子序列集合中 temp.add(nums[i]); //继续向下执行 trackBack(i+1,nums,temp); //回溯到本层,移除之前添加的元素,使其在进入本层时的初始状态不能发生变化 temp.remove(temp.size()-1); } } ```
{{ item.content }}
{{ child.content }}