清溪镇网站建设,网站建设费用属于什么科目,网页设计素材图片怎么获取,jsp网站开发职位要求目录
491 递增子序列
46 全排列 491 递增子序列 在dfs中进行判断#xff0c;如果path的长度大于1#xff0c;则将其添加到res中。 本题nums中的元素的值处于-100与100之间#xff0c;可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过#xff0c;…目录
491 递增子序列
46 全排列 491 递增子序列 在dfs中进行判断如果path的长度大于1则将其添加到res中。 本题nums中的元素的值处于-100与100之间可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过如果在此树层使用过则应该跳过本层循环来避免重复如果未使用过则可以将该元素添加到path中。 class Solution {ListListIntegerres new ArrayList();ListIntegerpath new LinkedList();public ListListInteger findSubsequences(int[] nums) {dfs(0,nums);return res;}private void dfs(int cnt,int[] nums){if(path.size() 2){res.add(new LinkedList(path));//这里不返回}boolean st[] new boolean[205];//nums中的元素位于-100到100之间,可以将其映射到0到200中,st用来记录此层元素是否被遍历过for(int i cnt;i nums.length;i){if(path.size() 0 path.get(path.size() - 1) nums[i])continue;//如果不能形成递增序列则跳过此层循环if(st[nums[i] 100])continue;//该树层出现过该元素,会导致重复,应该跳过此层循环st[nums[i] 100] true;path.add(nums[i]);dfs(i 1,nums);path.remove(path.size() - 1);}}
}
时间复杂度O(×n)
空间复杂度O(n)
46 全排列 由于本题需要返回所有可能的全排列可以设置布尔数组st记录当前数字是否被使用过如果未被使用过则将该数字加入到path中如果被使用过则应判断下一个数字。 class Solution {ListListIntegerres new ArrayList();ListIntegerpath new LinkedList();boolean st[];public ListListInteger permute(int[] nums) {st new boolean[nums.length];dfs(nums);return res;}private void dfs(int nums[]){if(path.size() nums.length){res.add(new LinkedList(path));return;}for(int i 0;i nums.length;i){if(st[i])continue;st[i] true;path.add(nums[i]);dfs(nums);path.remove(path.size() - 1);st[i] false;}}
}
时间复杂度O(n×n!)
空间复杂度O(n)
