文章目录
- 491.递增子序列
- 思路
- 思路代码
- 官方题解
- 代码
- 困难
- 46.全排列
- 思路
- 思路代码
- 困难
- 47.全排列 II
- 思路
- 思路代码
- 困难
- 今日收获
491.递增子序列
491.递增子序列
思路
同样有去重和树节点需求,但与之前的排列不同的是,这次子序列要和原题一致,所以不能采用排序和used数组的方式。
同树层选择map字典记录使用过的树,如果被使用过或者非递增,continue
if used[nums[i]]||(len(path)>0&&nums[i]<path[len(path)-1]){continue}
枚举子序列2的n次方,写入需要n,所以时间复杂度
O ( 2 n ∗ n ) O(2^n*n) O(2n∗n)
思路代码
func findSubsequences(nums []int) [][]int {res:=[][]int{}path:=[]int{}var backtrack func(startindex int)backtrack = func(startindex int){if len(path)>=2{temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)}used:=make(map[int]bool)for i:=startindex;i<len(nums);i++{if used[nums[i]]||(len(path)>0&&nums[i]<path[len(path)-1]){continue}used[nums[i]]=truepath = append(path,nums[i])backtrack(i+1)path=path[:len(path)-1]}}backtrack(0)return res
}
官方题解
思路相同,不止可以用哈希表去重,由于数的范围是有限的,也可以用数组来模拟字典。
代码
var (res [][]intpath []int
)
func findSubsequences(nums []int) [][]int {res, path = make([][]int, 0), make([]int, 0, len(nums))dfs(nums, 0)return res
}
func dfs(nums []int, start int) {if len(path) >= 2 {tmp := make([]int, len(path))copy(tmp, path)res = append(res, tmp)}used := make(map[int]bool, len(nums)) // 初始化used字典,用以对同层元素去重for i := start; i < len(nums); i++ {if used[nums[i]] { // 去重continue}if len(path) == 0 || nums[i] >= path[len(path)-1] {path = append(path, nums[i])used[nums[i]] = truedfs(nums, i+1)path = path[:len(path)-1]}}
}
困难
非递增序列取子集去重问题,字典记录每次递归的同树层元素。
46.全排列
46.全排列
思路
不同于组合问题,不需要startindex,但是需要记录已经选择的数,递归的时候从剩下的未选择的数中选。
时间复杂度On*n!
思路代码
func permute(nums []int) [][]int {res:=[][]int{}path:=[]int{}used:=make([]bool,len(nums))var backtrack func()backtrack = func(){if len(path)==len(nums){temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)return}for i:=0;i<len(nums);i++{if !used[i]{path=append(path,nums[i])used[i]=truebacktrack()used[i]=falsepath=path[:len(path)-1]}}}backtrack()return res}
困难
不需要记录startindex,每次都从头开始,但排列问题需要一个used数组,标记已经选择的元素。
47.全排列 II
47.全排列 II
思路
需要去重,和之前组合去重思路相同,used数组去重同树层数。
思路代码
func permuteUnique(nums []int) [][]int {res:=[][]int{}path:=[]int{}used:=make([]bool,len(nums))sort.Ints(nums)var backtrack func()backtrack = func(){if len(path)==len(nums){temp:=make([]int,len(path))copy(temp,path)res=append(res,temp)}for i:=0;i<len(nums);i++{if i>0&&nums[i]==nums[i-1]&&!used[i-1]{continue}if !used[i]{used[i]=truepath=append(path,nums[i])backtrack()used[i]=falsepath=path[:len(path)-1]}}}backtrack()return res}
困难
used数组中的数i如果为true代表在递归过程中使用过,如果i-1为false代表在同树层遍历过程中使用过。
今日收获
非递增序列取子集去重问题,字典记录每次递归的同树层元素。
排列问题同样需要used数组:
used数组中的数i如果为true代表在递归过程中使用过,如果i-1为false代表在同树层遍历过程中使用过。