代码随想录算法训练营第二十九天| 491 递增子序列 46 全排列

目录

491 递增子序列

46 全排列

---

491 递增子序列

在dfs中进行判断，如果path的长度大于1，则将其添加到res中。

本题nums中的元素的值处于-100与100之间，可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过，如果在此树层使用过，则应该跳过本层循环来避免重复，如果未使用过则可以将该元素添加到path中。

class Solution {List<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList();public List<List<Integer>> 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 {List<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList<>();boolean st[];public List<List<Integer>> 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)