网站效果代码,餐饮公司网站模板,它有什么特点,龙岩网红491.递增子序列 给定一个整型数组, 你的任务是找到所有该数组的递增子序列#xff0c;递增子序列的长度至少是2。 示例: 输入:[4, 7, 6, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [6, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数…491.递增子序列 给定一个整型数组, 你的任务是找到所有该数组的递增子序列递增子序列的长度至少是2。 示例: 输入:[4, 7, 6, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [6, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中可能包含重复数字相等的数字应该被视为递增的一种情况。 在子集中我们是通过排序再加一个标记数组来达到去重的目的。而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑。本题抽象为树结构过程如下
从上图可以看到如果在同一个父节点下同一树层使用过的元素便不再取如果所取元素小于子序列最后一个元素也不符合条件。因此可以设置一个哈希集合来记录当前所取的值是否被使用过哈希集合在递归后不用回溯因为记录的是同一树层的使用情况新的循环会清空重新记录。
class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public void backTracking(int[] nums, int startIdx){if(path.size()1){res.add(new ArrayList(path));}HashSet record new HashSet();for(int istartIdx;inums.length;i){/*如果path不为空且当前元素小于path最后一个元素则不取如果元素的值使用过不取*/if((!path.isEmpty() path.get(path.size()-1)nums[i]) || record.contains(nums[i])){continue;}record.add(nums[i]);path.add(nums[i]);backTracking(nums, i1);path.removeLast();}}public ListListInteger findSubsequences(int[] nums) {backTracking(nums, 0);return res;}
}
46.全排列 给定一个 没有重复 数字的序列返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 排列问题不需要使用startIdx因为可以存在重复取值的情况比如第一次1被取过形成[1,2,3]后面还可以再取组成[2,1,3]但是需要设置一个数组used来记录当前元素在同一path中是否使用过。如果used[i-1]为true则取下一个元素因为本题为不重复的元素所以不用去重。
class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public void backTracking(int[] nums, boolean[] used){if(path.size()nums.length){res.add(new ArrayList(path));return;}for(int i0;inums.length;i){/* 如果used[i-1]为true说明同一树枝上使用过值一样的元素如果used[i-1]为false说明同一树层上使用过值一样的元素*/if(used[i]true) continue;used[i]true;path.add(nums[i]);backTracking(nums, used);path.removeLast();used[i]false;}}public ListListInteger permute(int[] nums) {boolean[] usednew boolean[nums.length];backTracking(nums, used);return res;}
}
注意在调用回溯算法的时候要记得创建一个used数组。
47.全排列 II 给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1 输入nums [1,1,2]输出 [[1,1,2], [1,2,1], [2,1,1]] 示例 2 输入nums [1,2,3]输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 本题和上一题的区别在于有重复的数字所以需要去重先对数组进行排序设置used数组记录是否使用过如果used[i-1]为true说明同一树枝上使用过值一样的元素如果used[i-1]为false说明同一树层上使用过值一样的元素。
import java.util.Arrays;
class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public void backTracking(int[] nums, boolean[] used){if(path.size()nums.length){res.add(new ArrayList(path));return;}for(int i0;inums.length;i){/*当 used[i-1] used[i]时used[i-1]为true说明同一树枝使用过若为false说明同一树层使用过*/if(used[i]true || (i0 nums[i-1]nums[i] used[i-1]false)){continue;}used[i]true;path.add(nums[i]);backTracking(nums, used);path.removeLast();used[i]false;}}public ListListInteger permuteUnique(int[] nums) {Arrays.sort(nums);usednew boolean[nums.length];backTracking(nums, used);return res;}
}
