天河网站设计,免费微网站系统源码,wordpress前端怎么写,孝感网站建设专家回溯
1、39. 组合总和
题目#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的…回溯
1、39. 组合总和
题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]]
思路
第二次写了很简单就写出来了注意 2 可以使用多次。_backtrack(res, list,candidates, target,sum, i1),不要i1
func combinationSum(candidates []int, target int) [][]int {// 代码二刷很经典回溯list : make([]int, 0)res : make([][]int, 0)backtrack(res, list,candidates,target,0,0)return res
}
func backtrack(res *[][]int, list,candidates []int, target, sum,index int) {if sum target {ans : make([]int, len(list))copy(ans, list)*res append(*res, ans)return}if sum target {return}for i : index; ilen(candidates); i {sum candidates[i]list append(list, candidates[i])backtrack(res, list,candidates, target,sum, i)sum - candidates[i]list list[:len(list)-1]}
}2、40. 组合总和 II
题目 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。 输入: candidates [10,1,2,7,6,1,5], target 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
思路
怎么去重呢?使用 historyelse if sum target 记得这个也要剪枝避免无效运算导致的超时 func combinationSum2(candidates []int, target int) [][]int {// 代码二刷sort.Ints(candidates)history : make([]bool, len(candidates))list : make([]int, 0)res : make([][]int, 0)backtrack(res, list,candidates,target,0,0,history)return res
}
func backtrack(res *[][]int, list, candidates []int, target, index, sum int,history []bool) {if sum target {ans : make([]int, len(list))copy(ans, list)*res append(*res, ans)return} else if sum target {return}for i:index; ilen(candidates); i {if i1 candidates[i] candidates[i-1] history[i-1] false {continue}sum candidates[i]list append(list, candidates[i])history[i] truebacktrack(res, list, candidates, target, i1, sum,history)sum - candidates[i]list list[:len(list)-1]history[i] false}
}3、131. 分割回文串
题目 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 输入s “aab” 输出[[“a”,“a”,“b”],[“aa”,“b”]]
思路
细节注意i:index注意其实回文很简单带入例子就明白了*res append(*res, ans)注意是 ans为什么呢
func partition(s string) [][]string {// 代码二刷条件就是判断是否为回文字符串list : make([]string, 0)res : make([][]string, 0)backtrack(res, list, s, 0)return res
}
func backtrack(res *[][]string, list []string, s string, index int) {if index len(s) {ans : make([]string, len(list))copy(ans, list)*res append(*res, ans)return}for i:index; ilen(s); i {if huiwen(s, index, i) {list append(list, s[index:i1])backtrack(res, list, s, i1)list list[:len(list)-1]}}
}
func huiwen(s string, left,right int) bool {for leftright {if s[left] ! s[right] {return false}leftright--}return true
}
