黑龙江网上建设局报建网站,常熟网站建设都找聚尚网络,wordpress插件 知乎,文案代写回溯
1、491. 递增子序列
题目#xff1a; 给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以…回溯
1、491. 递增子序列
题目 给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
思路
if len(list)0去重很经典的去重方法,但这次去重不一样了是在内部写的 used真的是不带入例子很难理解不是if len(list)0 || nums[i] nums[i-1] {是 nums[i] list[len(list)-1]
func findSubsequences(nums []int) [][]int {// 代码一刷list : []int{}res : make([][]int, 0)var backtrack func(res *[][]int, list,nums []int, index int)backtrack func(res *[][]int, list,nums []int, index int) {if len(list) 2 {ans : make([]int, len(list))copy(ans, list)*res append(*res, ans)}used : make(map[int]bool, len(nums))for i:index; ilen(nums); i {if used[nums[i]] {continue}if len(list)0 || nums[i] list[len(list)-1] {used[nums[i]] truelist append(list, nums[i])backtrack(res, list, nums, i1)list list[:len(list)-1]}}}backtrack(res, list, nums, 0)return res
}2、46. 全排列
题目 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
思路
其实难点就在于这个选择列表理解记忆一下,带入秒懂画图
func permute(nums []int) [][]int {// 代码二刷res : [][]int{}list : []int{}vis : make([]bool, len(nums))backtrack(res, list,nums, vis)return res
}
func backtrack(res *[][]int, list []int ,nums []int, vis []bool) {if len(list) len(nums) {ans : make([]int, len(list))copy(ans, list)*res append(*res, ans)return}for i:0; ilen(nums); i {if vis[i] {continue}list append(list, nums[i])vis[i] truebacktrack(res, list, nums,vis)list list[:len(list)-1]vis[i] false}
}3、47. 全排列 II
题目 给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 输入nums [1,1,2] 输出 [[1,1,2], [1,2,1], [2,1,1]]
思路
去重呗,回溯玩多了就是条件的玩法条件和一些选择列表以及去重方法的做法
func permuteUnique(nums []int) [][]int {// 代码二刷list : []int{}res : [][]int{}sort.Ints(nums)vis : make([]bool, len(nums))backtrack(res, list, nums, vis)return res
}
func backtrack(res *[][]int, list,nums []int, vis []bool) {if len(list) len(nums) {ans : make([]int, len(list))copy(ans,list)*res append(*res, ans)return}for i:0; ilen(nums); i {if vis[i] {continue}if i ! 0 nums[i] nums[i-1] !vis[i-1] {continue}list append(list, nums[i])vis[i] truebacktrack(res, list,nums,vis)vis[i] falselist list[:len(list)-1]}
}4、
题目
思路 5、
题目
思路
