手机端网站开发教程,交友平台,wordpress盗版插件盈利,网站怎么上传数据库第七章 回溯算法 491.递增子序列46.全排列47.全排列II代码随想录文章详解总结 491.递增子序列
同层去重#xff0c;只需保证当前层元素不重复即可【前仆后继的感觉】
func findSubsequences(nums []int) [][]int {res, path : [][]int{}, []int{}var help func(nums []int, … 第七章 回溯算法 491.递增子序列46.全排列47.全排列II代码随想录文章详解总结 491.递增子序列
同层去重只需保证当前层元素不重复即可【前仆后继的感觉】
func findSubsequences(nums []int) [][]int {res, path : [][]int{}, []int{}var help func(nums []int, startIndex int)help func(nums []int, startIndex int) {if len(path) 1 {tmp : make([]int, len(path))copy(tmp, path)res append(res, tmp)}used : make(map[int]bool, len(nums))for i : startIndex; i len(nums); i {if used[nums[i]]|| len(path) 0 nums[i] path[len(path)-1] {continue}path append(path, nums[i])used[nums[i]] truehelp(nums, i1)path path[:len(path)-1]}}help(nums, 0)return res
}46.全排列
used数组记录当前元素是否在path路径中存在若存在则跳过。一个值在一条path路径中只能被选取一次
func permute(nums []int) [][]int {res : [][]int{}path : []int{}used : make([]bool, len(nums))var help func(nums []int, index int)help func(nums []int, index int) {if len(path) len(nums) {tmp : make([]int, len(path))copy(tmp, path)res append(res, tmp)}for i : 0; i len(nums); i {if used[i] true {continue}path append(path, nums[i])used[i] truehelp(nums, i1)path path[:len(path)-1]used[i] false}}help(nums, 0)return res
}47.全排列II
上题扩展有重复元素。先排序然后同层剪枝 同层剪枝i 0 nums[i] nums[i-1] used[i-1] false跳过 当nums[i-1]作为某一层元素其所有的递归选择已经穷尽回溯时才会有used[i - 1]false。因此当nums[i] nums[i-1]跳过否则nums[i]递归得到的结果与nums[i - 1]结果重复
func permuteUnique(nums []int) [][]int {res : [][]int{}path : []int{}used : make([]bool, len(nums))sort.Ints(nums)var help func(nums []int, index int)help func(nums []int, index int) {if len(path) len(nums) {tmp : make([]int, len(path))copy(tmp, path)res append(res, tmp)return}for i : 0; i len(nums); i {if i 0 nums[i] nums[i-1] used[i-1] false || used[i] true {continue}used[i] truepath append(path, nums[i])help(nums, i1)path path[:len(path)-1]used[i] false}}help(nums, 0)return res
}代码随想录文章详解
491.递增子序列 46.全排列 47.全排列II
总结
常做常新是怎么回事 代码随想录图示帮助好大
